you might check out: MySQL Benchmark Suite

I notice they have a benchmark listed that a 2mil row indexed read shows a time of 367 seconds.

I suspect that you might be reaching the limits of mySQL, or at least the limits that guarantee "acceptable" response times.