Good question!
Let's take a look at the Gmail desktop site:
Multi-selection is always available, simply click on one of the checkboxes at the start of an email item in the list.
Selecting "all" will only select the items displayed on the current page.
If you move to a different page, you can select one or more items on that page without affecting the selection on other pages. I.e. multi-selection exists across pages.
When you select an action on any page, it only affects the items selected on that page. I find that weird and annoying (when attempting to delete or move multiple items), however it does dodge, in ways, the problem of having to convey the status of selections on pages other than the one currently being observed.
Once an action has been performed, a Snackbar appears providing an option to Undo the change. Pressing undo will revert the changes while clearing the multi-selection only on the current page.
Note, Gmail on mobile (Android) also makes multi-selection available at all times (using checkboxes), which is counter to the traditional method for multi-selection on Android (longpress with a Contextual Action Bar), and while its content is paginated, those pages all manifest within the one "endlessly" scrolling list. Gmail for Android then differs from the desktop experience:
A counter is shown in the AppBar indicating the number of selected items (across all pages).
There is no option to select all...given the behaviour on mobile, that would pose a problem: should selecting all select items from pages that have not yet been loaded or only all the loaded items?
Choosing an action while multiple items are selected across "multiple pages" will affect all selected items.
A Snackbar with Undo option is displayed on Android. Using undo will revert changes but also lose all selections.