ImageMagick is comparatively slower than other Graphics Packages. It is NOT the problem of PerlMagick (Image::Magick).

A possible problem is Environment variables. The CGI has a different environment than that of command-line. The environment variables are set in two ways.

1. Set directly by Apache
2. Passed by OS

In some cases apache will suppress some environment variables from being passed. It can caused problems.

you can workaround this problem by passing environment using PassEnv directive in your httpd.conf ( in your virtual host section ) to pass the named environment variables to CGI scripts instead of suppressing them.
Try using

PassEnv MAGICK_HOME
[download]

and its value, will become available to CGI scripts.

check with your /ImageMagick/im-faq.tgz or /ImageMagick/im-faq.zip. for more details.
The zip file contains im-faq.pod and .html, im-faq-1.cgi and env.cgi.

Updates:
This FAQ is available here

Cheers !

--VC