Are you absolutely sure that it's the same SQL statement that produces such great differences between DBI and the command-line client? Not that a Perl-caused slowdown is out of the question, but that's always the first thing I'd double-check.

If you're getting back a ton of data from each query, then a slowdown in Perl is quite likely, especially if you're using fetchrow_array. Take a look at Speeding up the DBI, which has recipes for faster ways to fetch lots of data. However, it sounds like the slowdown happens even when no data is returned. In that case, you should do some careful DBI profiling. Most likely most of the time is spent waiting for the MySQL server's slow response..