A circuit diagram of your setup, particularly including your MOSFET driver would be really nice. However, I'll go out on a limb here and suggest that you need to look closely at your drive circuits. It is entirely possible that you are driving your MOSFET gates from 3.3 volt logic. This is perfectly doable - as long as you are using MOSFETs with logic-level gate thresholds. A lot of power MOSFETs need a minimum of 4 volts on the gate to ensure full turn-on. If you're only giving it 3.3 volts, it will only turn on partially, and will dissipate too much power. It's important that you realize that operating a transistor within both voltage and current limits can still kill it if you don't get rid of the heat dissipated, and at high currents it's easy to generate too much heat.
There is a quick check for this (if you want physical proof): Get ready to sacrifice one more MOSFET, but hey, who's counting, right? Drive a heating element full on. Quick like a bunny, measure the voltage across the nichrome and the voltage across the MOSFET. If your MOSFET voltage is not less than about 10% of the nichrome voltage, you're doing something wrong, and less is better in this case. You don't mention your drive voltage, but it has to be less than 25 volts. Let's say it's 20 volts, and let's say the current is 10 amps - this is just to illustrate, OK? Then total power dissipated is 200 watts, and the effective resistance of the total load is 2 ohms. If your MOSFET is fully on, I'd expect an Rds of .1 ohms or less (and this will give a MOSFET voltage about 5% of the nichrome voltage). This would provide a MOSFET dissipation of 10 watts. Without a heat sink, this would kill the MOSFET, so you need a heat sink in any case. And this better not be one of those little U-shaped jobbers, either. You need real heat sink, possibly with a fan. With more airflow you can use a smaller heat sink.
You need to consult the data sheet for your MOSFET to determine both Vgs(th),the threshold gate voltage, and Rds(on), the on-resistance when the gate is properly driven. Then you will need the specs on your heat sink, specifically the thermal resistance to ambient. You will also need to do a little research on how to specify a heat sink.
As for some of your other questions, consider the two voltages you measured. If they both add up to the nominal voltage of your drive converter, you are not drawing too much current, and you don't have a short. You are just fatally abusing your MOSFETs.
A linear regulator reduces voltage by acting like a variable resistance. As a result, it dissipates energy proportional to the voltage difference times the current - in this case, (19 volts - 3.3 volts) * 500 milliamps, which is nearly 8 watts - a lot of heat to dissipate in a small package.
For applications like this with a large voltage difference or high power requirements, you should use a switching regulator. Switching regulators can regulate voltages up or down without wasting the bulk of the power - they operate at efficiencies as high as 90%, which means you can expect waste heat on the order of 0.2 watts instead.
Assuming this is a one-off application, you can find prebuilt switching regulator 'buck' (voltage reducing) modules on EBay quite affordably.
Best Answer
There is no inductive heating since water is not magnetic (in any working sense). So if only an insulated wire contacted the water there would be no current flow and no heating. So your story (if no wire contacts the water) is incorrect, but since power wiring panels have lots of bare voltage carrying conductors in them, I assume it's just someone got it wrong.
Providing the water is impure enough to conduct there will be current flow and therefore heat generated in the water if the wires contact the fluid. Depending on the voltage available there is likely to be lots of heat and steam. There are many (mostly Chinese) shower and water heaters that use this very method, although it is potentially hazardous.