No entiendo porque se complican tanto, no existe persona en el mundo que necesite 1 millón de registros para procesarlos o leerlos.
Siempre cuando se tienen tantos datos se usan filtros para ir agrupandolos por tipos y manipularlos.
El paginador de el GridView carga todo en memoria lo que no es para nada un paginador funcional que se recomiende su uso.
Te dejo este artículo donde explican como paginar con Sql Server 2005 usando casi el mismo método de Mysql.
http://www.dotnetpanama.com/dotnetpa...QL-Server.aspx
Saludos,