Laravel counts the total amount of rows that a paginator must use by re-issuing your query with a COUNT(*) statement instead. This is and should be the "default" way to do things, but in MySQL there's a more performance-efficient way via SQL_CALC_FOUND_ROWS and FOUND_ROWS().
I've created a small patch that hacks Laravel to use these functions which may increase performance for you depending on your use. They work with my version which is currently 4.0-dev (2aea469f0c49ede7994cc27f68fcdd658d4d15e2) from the 1st of September 2013. It will most likely break at some point in the future. Perhaps Taylor will add a way to implement this in a more clean way. Perhaps not.
Note: The patch also contains a fix for issue #2225