Sorry if I ramble on, just making sure I give enough background first 
This is my current project. In the top left are 6 motor controls, needing a PWM and DIR input. Power is distributed around the board on the top right (with all the capacitors on), which sends 12v from a SLA battery to the system. At the bottom are two MEGA's side by side with an accelerometer in the middle (red LED), and a stack of 12V regulators in front. In the middle on the right, is a 3 pin current sensor.
The 12V regulators have a center-positive barrel connector attached which goes into each MEGA. Using a voltmeter, I get around 11.98v from these. The regulator gets warm at best when in use.
The MEGA on the right has a ethernet shield on top.
My issue is that as its currently set up, the MEGA 5v regulator on the right gets uncomfortably hot with no code running, while the one on the left is nice and cool. I thought the Arduino could deal with 5-12v comfortably? How hot can this regulator get before it fails?