The circuits that perform addition and subtraction can be reused in the circuits shown in this page : http://fourier.eng.hmc.edu/e85_old/lectures/arithmetic_html/node8.html
Multiplication and division require a shift register that is large enough to store the product or dividend. In the case of multiplication, I tried to redesign it in my head but I stumbled on the problem of the carry... The below drawing (taken from the link above) solves it finally :-)
For a 16-bits multiplicand, the shift register needs 32 bits. The carry counts as a 33rd but it does not remain set at the end, at least for the unsigned multiplication. The maximal value is 0xFFFF×0xFFFF=0xFFFE0001
The multiplier should be loaded from the input so a row of relays is required to select the source of the input data. The accumulator (and carry) is cleared initially but another line of 16 relays must multiplex the accumulator's value to perform the shift, because in the add/sub mode, the accumulator is not shifted.
Division looks almost the same, but there's a catch.
The shift direction is reversed ! So that's 32 more MUXing relays ! (and 2A of consumption)
I have not yet decided if I'll implement restoring or non-restoring division. Both are possible because I can either add 0 or add/subtract at will, it's just a different control signal to toggle.
Overall, that's 64 relays for MUXing and 64 relays for the 32-bits shift register. 128 relays are added to perform the 4 operations. The ALU is 4×16=64 relays already, 192 relays are needed and I don't even count the control logic or the amplifiers !