Pagination With Row Count

I changed a stored procedure that does pagination from the top style to the
bottom style - mainly to avoid errors in differences in the 2 queries (count
and select) and for conciseness. The performance on a large table for the
bottom query was amazingly bad. The query plan is very different too. It
was about 25 times slower on a 1 million row table. I am familiar with
other pagination techniques (temp tables with identity, TOP-TOP, etc), but
is there a way to use the ROW_NUMBER function AND get a count of records
back in a single query with decent performance?


-- -------------------------------------------------------------
USE NorthWind


DECLARE @cnt Int
SELECT @cnt = Count(*) FROM Customers


;WITH Cust AS
(
SELECT CompanyName, ContactName,
ROW_NUMBER() OVER (ORDER BY ContactName) AS rownum
FROM Customers
)
SELECT *, @cnt AS TRowCount
FROM Cust
WHERE rownum > 10
AND rownum <= 20
ORDER BY rownum
-- -------------------------------------------------------------
-- -------------------------------------------------------------
USE NorthWind


;WITH Cust AS
(
SELECT CompanyName, ContactName,
ROW_NUMBER() OVER (ORDER BY ContactName) AS rownum,
Count(*) OVER() AS TRowCount
FROM Customers
)
SELECT *
FROM Cust
WHERE rownum > 10
AND rownum <= 20
ORDER BY rownum
-- -------------------------------------------------------------