Hi,
I don't find a winning solution so I'm seeking for advice. In this bug report [0], we see that it's annoying to have incorrect page navigation (page selector and arrows) for InnoDB.
However, when I apply my proposed patch (which forces an exact count in sql.php), I see delays for larger InnoDB tables.
For example, on MySQL 5.5.31, the first time I browse a table having one million rows, I wait for 9 seconds. I tried with 0.5 million and it was about 5 seconds. A few minutes afterwards, even after closing the browser, my big table starts to display in two seconds.
I tend to find these delays acceptable and I propose to apply my patch.
[0] https://sourceforge.net/p/phpmyadmin/bugs/3976/