Arduino Mega Voltage Regulator Extremely Hot

The on-board regulator has the board as its heatsink - it can probably take upto a watt or a little less - 3.5W is way beyond safe.

Most regulators detect over-temperature and shutdown automatically, which is probably what you see.

Add an external regulator with enough heatsinking?