It seems that an overheating computer is likely to cause freezes. Source: http://www.theguardian.com/technology/2006/jul/27/guardianweeklytechnologysection4 (and many fora suggest the same).
Considering your computer gets too hot even beyond the recommended temperature specified by Intel, there is a reasonable chance you are causing damage to your CPU.
It is clear that the computer repair shop messed up. This means that they should either fix it properly or give you a refund. Depending on the specific model you have, the repair should not be too complicated, so doing it yourself is an option as well. In any case, it should be easy to find someone who can do it.
If you specify your model, I could point you to the right instruction manual and tell you how easy the fix would be to do yourself. If you don't dare to do it yourself, perhaps let a handy colleague or friend do it with help of the manual.
With this model, it is not difficult to do the repair yourself. Look for "1060 Fan assembly" in the pdf from the following link: https://support.lenovo.com/us/en/docs/migr-75051
There are plenty tutorials how to apply thermal paste on the internet, just beware that you only have to use a tiny bit.