Here's how I'd proceed:

1. Open up 'top' in a window and run the script. Does mysqld stay on the CPU 100% of the time? Or is it mostly Perl? Or a mix of the two?
2. If mysqld is eating most of the CPU time I'd bust out DBI::ProfileDumper and see what the hot queries are. Then fix them and repeat.
3. If it's mostly Perl I'd setup Devel::DProf (unless it seg-faults, and then I'd try Devel::Profiler). That will tell you what the hot subroutines are. Fix them to work faster and repeat.

The important thing to keep in mind is that you're not trying to speed up the whole program, just the slow part. Finding the slowest part is your first priority, then you'll know where to focus your attention.

-sam