Since no other than @Ramhound responded and I fixed the problem, I thought I should post it as an answer. I couldn't exactly pinpoint what the problem was, but I have a good idea of the root causes. I followed these steps and successfully removed VS2010 and 2012 and installed 2013 successfully.
1) Removed C++ redistributable from Programs and Features. There were many versions of it including the same one for x64 and x86. Removed almost all of them.
2) Then I manually removed some of the extra VS tools that came with the initial install. I deleted about 7-8.
3) Instead of going straight to the forced uninstall, I ran a repair on the original setup file. I think this was the step that saved me after removing all the packages and tools from Steps 1 and 2.
4) Created a restore point manually
5) Turned off Windows Defender and the System Restore Point creation. I don't think this helped much to be honest as the uninstall still said 'Creating System Restore point'
6) Then I started the forced uninstall and it was successful.
A good place to start is removing all the unnecessary VS tools that you don't use.