The only thing I can find is that the power supply takes 5 - 12v dc or up to 20v at the max.
The processor and other circuitry on your Mega all runs at 5v. There is an on-board regulator that takes your 12v supply and regulates it down to 5v for the processor.
The problem is that the type of regulator used on the Mega is not very efficient.. To get from 12v to 5v, it has to burn off more than half the power as heat. That is not a big deal if you are running the Mega by itself, since the Mega doesn't use a lot of power. But when you start adding a lot of other circuitry, the amount of power that has to be dumped as heat increases as well. At some point, the regulator will overheat and shut itself down.
LED strips are pretty power hungry and they run off 5v too. I would recommend giving them their own supply to ease the burden on your Mega's regulator. This would be a good choice: http://www.adafruit.com/products/276