If you have enough memory, and you're using Apache, you may want to look into using mod_perl.

Although there may be some quirks to deal with, it'll keep one copy of each module in memory, that all of the CGIs can share, so there isn't the loading and teardown for each page call.

Of course, this won't solve the general case of the issue that you're seeing (the answer to that is to not 'use' modules up front, but 'require' them as you need them, and then import the functions that you need, (if any, as you said you were using fully qualified functions).

As you've said you're using fully qualified function calls, you may have a leg up on the second approach.