I've invested several months of my life optimizing arbitrary sort and filter for MySQL results over tables varying from 100k rows to 100M (using time windows to scope things). As long as you can efficiently cut down the underlying data set into the region of 100k using some kind of window - usually recency based - and convince MySQL to filter by this before it sorts or does any other kind of filter - then limit / offset pagination doesn't hurt.
You can then use higher-level pagination on the recency window if it becomes necessary.