PostgreSQL teve funções de janela por um tempo agora, que pode ser usado para fazer muitas coisas, incluindo contar linhas antes que LIMIT seja aplicado.
Com base no exemplo acima:
SELECT stuff,
count(*) OVER() AS total_count
FROM table
WHERE condition
ORDER BY stuff OFFSET 40 LIMIT 20
