Paginate has a pseudo-list layer to unify the various collection types (list/tuple, SQLAlchemy query, SQLAlchemy select, custom sequence). This makes it hard to tell what each backend is doing, and how Python's special methods are interacting with the backend, or whether an object is missing a special method and whether it should need it.
Refactor paginate to eliminate the emulated lists. Instead each backend should have a helper class that does its business in a straightforward manner and returns a Page or the data needed to create a Page. The Page itself can remain a list subclass but its data would be static. Also provide a mechanism for users to provide their own helper classes for unsupported collection types, perhaps by passing in a helper instance to the constructor. If not specified, fall back to the built-in helpers, which could either have a boolean method or raise an exception to indicate the collection is incompatible with it.