I had this very problem and my first reply to you is YES IT IS OVERHEATING but not in the way you would notice it. Please read the following as I solved this problem for the cost of a Penta Screw driver set and some arctic silver thermal compound.
On my late 2013 Macbook pro Resetting PRAM or NVRAM did not fix random shutdown faults . I tried this as a first option including resetting the SMC on my Macbook. Did lots of hardware tests to no avail, nothing seemed to be faulty.
One thing I found was that booting up in SAFE MODE stopped the random shutdowns. This led me to two conclusions, one that there was some corrupt driver or software causing the shutdowns in NORMAL MODE or some nasty malware had gotten onto my Mac. So wiped the SSD and reinstalled a fresh OSX, but to no avail, still random shutdowns in normal mode with no shutdowns in safe mode.
Finally I decided that maybe the amount of processing power in Safe mode used was less than in normal mode. So I began to suspect maybe the cooling system on the Macbook was faulty. Pulled the Macbook apart and took off the fans and heatsink. There it was !!! the thermal paste had turned to dust !!! so I cleaned it off with alcohol, put some Arctic Cooler paste on the CPU / GPU, just a dab on each is perfect. Put the heatsink back on, cleaned out the fans and vents and ran some stress tests in normal mode. Worked like a dream, problem solved !! The reason it was turning off was that the CPU/GPU were overheating and the heatsink wasn't drawing away the heat. So the Mac would seem to get hot at all for this very reason. The automatic shutdown in the CPU or GPU would kick in over a certain temperature and the CPU would shut down or the GPU would lock up and give a dark grey screen but with the computer still working. Either of these two symptoms can indicate a cooling issue.
I suspect Apple use very low quality thermal paste in order to save money, and over time this degrades and becomes dust as the computer heats up. This is great for them because then people will just go and buy a new mac thinking it's broken. By the way, I phoned Apple helpdesk, their advice for sorting the problem was to clean out my caches, totally idiotic as I told them I run Mac Cleaner which does this regularly. They had no other option apart from replacing the MOBO and Battery, which is more cash for them. By the way, run a fan controller on you macbook such as Macs Fan Control and set it to run on bootup. You'll need to set the temperature it starts to cool the computer at, to around 35 degrees celsius or less. This will ensure your macbook doesn't heat up again, but the fan noise will be audible, very slightly, whereas normally it will be totally silent, because the 2 fans running very slowly.
Hope this helps. There are online videos on youtube showing you how to take the macbook apart and fix it yourself with minimal tools. Apple hate this as they can't make money out of people. If it's under warranty, take it to a repair shop but if it's out of warranty, you could be up for a very hefty bill if they tell you the motherboard and battery need replacement.
