The force that makes the armature in a relay move is created by ampere-turns.
Looking only at the coil, you have one degree of freedom when you fill the winding area fully (which, as it turns out, is the most efficient). You can have more turns of thin wire or fewer turns of thick wire. It also turns out that the power drawn by the relay will be approximately constant as you vary that degree of freedom. Your example is 720mW, so if you rewind the coil so that it is 100\$\Omega\$ then the nominal operating voltage will be more like 8.5V, and if you rewind the coil with thinner wire so that it's 400\$\Omega\$ then the operating voltage will be more like 17V.
Of course that's based on filling the winding space more-or-less completely. If you choose not to do that, then the operating power of the relay will be higher than optimal and you may need more voltage than calculated to reliably operate the relay, and the coil will get hotter (further increasing the resistance of the coil).
For example, if you simply removed turns of wire to halve the resistance, then you would need twice as much current to operate the relay. So the relay might operate on the same voltage (ignoring temperature coefficient of copper, and ignoring the fact that removing outer turns would reduce the resistance a bit faster than reducing the number of turns) but draw double the power.