Hey, Mike,
A temp table with a few million rows doesn't necessarily mean disaster, though it generally raises the question on what the need is. The bigger issue can be whether you're looking to actually return those millions of rows, or just a partial subset.
Not trying to oversimplify this - but if you're using SQL 2012, they added new capabilities called FETCH and OFFSET, to implement paging. It doesn't necessarily run any faster than CTE that uses ROWNUM to grab an offset number of rows, but it doesn't require a CTE.
There are certainly times where, in a long and complicated proc, I'll retrieve X number of rows into a #Temp table, and then have to do several things with that #temp table before returning the result set.