My suggestion is to try TokuDB storage engine on that table. Our (admittedly text heavy) workload got order of magnitude scalability improvements and a dramatic fall in query times.
Table size 10GB and rows 12 Million
Also note that I am using the default settings of Tokudb
With Tokudb - 1 min 41.38 sec With Innodb - 58.17 sec
So almost double.