Here are the tests I would do if I were getting your symptoms....
[ ] Yes [X] No Does the Arduino heat up and shut down with the motor controller shield completely disconnected?
[X] Yes [ ] No Does the Arduino heat up and shut down with the motor controller shield connected but the motor disconnected?
[X] Yes [ ] No Does the Arduino heat up and shut down with the battery connected directly to the motor shield?
So yes, it starts heating up even if there is no motor connected. For the last one - "Does the Arduino heat up and shut down with the battery connected directly to the motor shield?" it actually doesn't matter where I have the power going - if it goes to the motor shield and I use the jumper on the shield it actually connects the power from the the motor shield and powers up the arduino. The same applies if I have it connected to the arduino instead. If the jumper is ON it simply connects both the shield and the arduino. If the jumper is removed though, then you only power what you have powered. In every case the arduino's voltage regulator gets hot.
In the above tests I have used the battery (12v) and a DC adaptor 12V 2000mA. It doesn't matter which one I use -both makes the voltage regulator hot. I didn't waited too much as I don't want to run it too long hot like that.
That's why I wanted to use external voltage regulator just to power the arduino separately.
Thanks.