I guess this all depends on the other features you have provided with the table.
For example, you have a table with more data than any human can assimilate effectively just using pagination.
I have a table consisting more than thousands of data.
So your table should have additional features to help the human find the records they are interested in. Features like:
- Basic Search
- Advanced search
- Ability to change the number of records per page ( plus Show All)
You should be considering the different patterns that exist to help the human find what they are looking for. Patterns like faceted search (aka guided search).
So while you have framed the problem as how to make it easier to select lots of records without it being annoying, this is actually the end of the story - the story starts when the human decides to work with some records, so you need to provide features that change thousands into something a lot smaller.
I recommend reading Search Patterns by Peter Morville & Jeffery Callender.