Pela minha experiência, a paginação é sempre mais rápida se deixada no banco de dados. Afinal, um banco de dados é construído para consultar e manipular grandes quantidades de dados.

Se você retornar grandes quantidades de dados em .NET e "armazená-los em cache" na sessão, rapidamente ficará sem memória em seu servidor.