There's no such thing as 'BIOS overheating' - what you're seeing is a badly worded message saying the BIOS has shut the system down to prevent CPU overheating.
From your symptoms the most likely problem is the contact between the CPU and the heatsink or a broken heatpipe. To confirm this, you'd expect to see cool or warm, but not hot air coming out of the exhaust vent even when the fan is running at full speed.
You'll need to replace the thermal paste between the processor and the heatsink, and if that doesn't solve it, the heatsink itself. Given you say you've cleaned the processor area I assume you've managed to take it apart, but if not, here's a starting point:
https://www.youtube.com/watch?v=HVpi4tJQL3w
Plenty more guides can be easily found:
https://www.google.co.uk/search?q=replace+thermal+paste+hp+g62