Thanks for thinking about it. :)
This isn't the pure-SQL version I was thinking of, but I am getting a total response time from my test code below < .5 seconds. I'll plug it into my production stuff and see what I get.

For the test, I greated a table of GUID strings (4.5 million rows) and made a simple index on the table.

Clear

? Seconds()   && 71292.415 seconds
cOrigTable = Sys(2015)
cTmpTable = Sys(2015)
cPageTable = Sys(2015)
USE "e:\guids.dbf" Alias (cOrigTable) Shared noupdate In 0
Select cGUID , Int(000) as iRowID from (cOrigTable) ;
	Where cGUID="AA" Top 500 Order by cGUID into Cursor (cTmpTable) ReadWrite

iOldArea = Select()
Select (cTmpTable)
Replace all iRowID with Recno()
? Seconds()   && 71292.815 seconds
Select (iOldArea)

Select * from (cTmpTable) Where iRowID Between 40 and 80 into cursor (cPageTable)
CursorToXML( (cPageTable) , "cMemVar" , 3 , 2+8 , 0 , "1" )
StrToFile( cMemVar , "e:\pagingresult.xml" )
USE In (cTmpTable)
USE In (cPageTable)
USE in (cOrigTable)
? Seconds()   && 71292.835 seconds