I don't understand this, there is nothing in Paintshop Pro that runs at startup. Do you mean uninstall, and not "install." Also could you be referring to the other program Paint Shop Pro Album, that does run a small program at start up.
May I ask why you uninstalled by removing the folder. What is wrong with Add/Remove programs. This would have removed it without any problem.
If it is the Album program, go to Start\Run and type in the box msconfig. Choose the Start up tab on the right, and untick anything relating to PSP. Click OK. Next time you start up you will get a message about Startup items. Choose not to display it again.
Or use this click here to stop it trying to run.