Arduino Mega and other modules power consumption
You can't fix it with more voltage. The board you are using (schematic here) uses a linear voltage regulator. All increasing the voltage does is make the regulator run hotter.

You could try running from around 7V, this will minimize the heat dissipation in the regulator and may allow you to pull more current through it but I suspect you've simply hit the design limits of the power supply circuits.

Instead of using the Arduino's built in power supply to convert from 12V to 5V you could try using an external 5V supply with a greater current capability connected directly to the Arduino 5V rail.