Modern computer processors will shut the computer down when the processor reaches a certain temperature to prevent burning up. Usually, it's a sudden power off when this happens.
Sounds like your CPU fan is failing.
I suspect that you are right. I opened the case with the power on, and the CPU fan was turning much slower than its rated 2000 rpm. I'm going to try replacing the fan (its a 120 mm, 3-wire fan) and see what happens.