Well, you could try logging a timestamp when you start the Image::Magick work and again when you finish it. Make sure it really is the IM tasks that are slow.
Also, somemonk please correct me if I'm wrong, but I believe Image::Magick is outdated and using IM with system() may give better performance/compatibility. It's at least worth a try to see if it gives better performance when you're running in CGI.