Perl can be a touchy uninstall. Firstly uninstall then go in and delete the remaining folder. Also find any other perl58.dll files check your windows/system32 folder incase there is one in there. Then use a registry cleaner Eusing free registry cleaner will do the trick. Reboot the system install perl reboot the system again and the perl step is done. Every one of these steps should be done and from talking to tomahawkeer on this subject it looks like even the registry cleaner can fix the issue so make sure you do each and every step.
good luck hope it works