I had random shutdowns on an R540. I first cleaned the fan. Then new thermal paste on the CPU. Still random shutdowns. Then I replaced the mother board. Thought I had finally licked it. Then again, random shutdowns. I had one more thought. I looked carefully at the tiny board with the power button and tandom USB ports with a 10x lens. It appeared discolored around the switch pins. I ordered a replacement on eBay (rev 1, my original had no revisions). It now is working perfectly. So, before going as far as I did, try replacing this board first.
I hope this helps someone else from the pain and frustration I went through.