How did pagination come to be used?

Unknown. For first numbering of pages in book or codex form.
Around 1470-1499 for printed books made with numbers on pages.

The system was known since antiquity, as there we have some fragments that show page numbers.

Running pagination may have been invented as early as the codex form itself.

Foliation and pagination have probably both been known since the codex first proliferated: both systems appear in fragments from late-antique Greek codices. Neither system was ever widespread in Western European manuscripts, however […], even in the fifteenth century foliation could be regarded as a specialized practice. Some medieval foliation was probably added during production, as in at least one copy of the first full English translation of the Bible.

Oxford, Bodleian Library, MS Bodley 296: rectos of ff. 1–176 foliated in Roman numerals in both red ink and black ink.

However, not all medieval foliation is scribal: a fifteenth-century reader could foliate a twelfth-century manuscript. To further complicate matters, some medieval finding systems referred to numbered openings rather than leaves—in other words, each double-page, verso-and-recto spread in the book was a single numbered entity—and so when leaves are not explicitly specified, what reads as foliation might in fact be the numbering of openings. Most manuscript codices which survive today are foliated, and most related scholarship uses folio numbers for reference, but the foliation involved is normally the work of modern owners or librarians. Why did foliation and pagination become standardized quite late, after being used by at least some producers early in the codex’s history?

By the century’s end pagination had supplanted foliation and become a standardized practice. At roughly the same rate, though beginning a few decades earlier in the 1470s, Arabic numerals displaced Roman numerals in print for both numbering practices. One possible explanation for pagination’s spread is that its greater granularity attracted humanist printers and readers, who found that precision useful when handling texts in the more challenging language of Greek.27 Pagination has changed little since its standardization, and is now a universal expectation in books, where it can usually be found ‘on the right side of the leef, in the higher part of the margyn’.
_{– Daniel Sawyer: "Page Numbers, Signatures and Catchwords", in: Dennis Duncan & Adam Smyth (Eds): "Book Parts", Oxford University Press: Oxford New York, 2019. (p139–149)}

The first printed pagination book is then credited also as:

Arnold Ther Hoernen, Cologne, 1470 (Cologne’s second printer after Ulrich Zel). The book, Sermo in festo praesentationis beatissimae Mariae virginis (ISTC: ir00303000) is special in that it is the first (extant) book to include printed foliation (‘page numbers’*), here printed in the recto margins, half way down the page.
(src)

For an early example of 'numbering' on a manuscript:

𝔓1 (Papyrus 1)

The first page shows an alpha at the top header of the recto, signalling first page. A beta follows on the verso…
_{– Philip Wesley Comfort: "Encountering the Manuscripts: An Introduction to New Testament Paleography & Textual Criticism, B&H Publishing Group, 2005. p33}

The first page of that papyrus:

That quickly finding a certain page or passage in any book is massively helped by having also page numbers available should be quite self-evident when looking at these 'unwieldy' codices or 'books'. But it is said that the Protestant desire to argue against these Catholic heretics while following their own motto of sola scriptura gave a big boost to this idea of service to the readers, although not really standard for almost all until the 17th century. But the point is: how to most quickly quote a passage while pointing a finger onto a certain page in a certain book to prove the opponent wrong.

As for the sequence:

Pagination is the consecutive numbering of book’s pages on both the recto and verso—front and back—sides. Pagination supplanted foliation, another type of sequential numbering; foliation denotes leaves on its recto side.

Most books before the 1500s lacked page numbers. Around 1450, less than an estimated ten percent of manuscript books contained pagination, but by the early 16th century, readers were relying on them to find their way through texts. As a modern reader, it is hard to imagine navigating a book without pagination, yet somehow people did for many centuries.

Scrolls
It may help to realize that page numbering was not a concept in the early history of the book due to the reading culture established by scrolls. Scroll culture lacked pagination because a scroll’s “text was continuous and lacked page breaks." Though Egyptians, Greeks, and Romans of antiquity divided scrolls’ text and images into columns called paginae, the emergence of the codex—a collection of leaves bound on one side—after the first century AD introduced a new organizational mode through pages.

Which is not entirely correct, though. Even scrolls had some pre-pagina 'find-tools'. In the case of Hebrew scripture, subdivisions for turning 'searching' into 'finding' were for example parashots. It's very noteworthy in that respect that Christians and Jews started quite late to add these other canonical finding aids and orientation markers within a book: titles, chapters and verses.

Codex
As Bonnie Mak points out in How the Page Matters, “as a single sheet, the page may stand free of an obvious attachment with others of its kind. The material boundaries of the solitary page not only circumscribe the space of communication, they also circumscribe the message itself; there is nothing more to be read than what is one the page."

Although the materiality of pages in a codex changed how readers approach a text, it still took a long time to shift reading culture and necessitate the use of pagination.

This is partly because page numbering was not necessary to produce a codex. Bookbinders did not assemble books by each page but instead dealt with groups of several leaves at once. To arrange these sections in the right order, binders marked each section with a letter of the alphabet, usually in the bottom right corner of the recto sheet. Numbers followed the letters to indicate the sequence of the leaves. Considering that this mark, called a “signature,” contained a combination of letters and numbers, and also considering that sections might have had an unequal number of leaves, these signatures were primarily for the artisans’ reference and not for the convenience of readers. However, the custom of signature marks may have been a predecessor to pagination, as the earliest examples of pagination have no signatures, and vice versa. Such an example is the book pictured in Figure 1 published in 1488; while there are signature marks throughout the pages, a book owner added his own page numbers in the top margins.
_{— Digital Book History: Page Numbers}

An important distinction regarding the "first printed book with page numbers": there is a difference between numbers foliated and paginated.

While the first foliated page numbers in printed books seem to appear indeed in the 1470s (further, early example of trying to ascertain 'the first'), but the real paginated page number is a bit later:

One of the most important achievements of the printed book is also a functional system of text indexing based on page counting and, more specifically, line counting. This allows for precise location of positions in all possible directories and registers.

Page counting has been known sporadically in the handwritten codex since the 12th century and has been common in Latin manuscripts since the middle of the 14th century, but especially in the 15th century (cf. Schneider 2004, p. 160). Like the parenthesis — an insertion in round brackets to structure the sentence structure — the foliation originated from German printers in Cologne (since the beginning of the 1470s), Augsburg, Ulm and Speyer and spread further to Strasbourg, Paris and Italy (cf. Saenger 1996, p. 275).

Pagination is reserved for letterpress printing (cf. especially Saenger 1996, pp. 256-279). Like the typographical paragraph, it goes back to Aldus Manutius, who first converted foliation into pagination in 1499.

Aldus needed the regular foliation or pagination above all for his numerous registers, which were added to the annotated classical editions in the appendix. His editions of Greek and Roman authors offered a smooth text on the page. Figure 5 shows one page of an index of a Greek Lucianus edition (Venice 1503).

^{Fig 5: Lucianus: Opera. Venedig: Aldus Manutius, 1503. 2° (Staatsbibliothek zu Berlin – Preußischer Kulturbesitz, Abteilung Historische Drucke, 4° Ald. Ren. 39,3): Registerseite mit Seitenverweisen}

Indexes to the works of Philostrat (the Elder and the Younger) and Callistratos, which are also included in this edition, are foliated in the order of their appearance in the book.
_{— Ursula Rautenberg: "Das Buch in der Codexform und einblättrige Lesemedien", in: Ursula Rautenberg & Ute Schneider (eds): "Lesen. Ein interdisziplinäres Handbuch/Reading: A Handbook", de Gruyter: 2015. (pp279–336; own translation, external links added)}

Related:
— Naomi S. Baron: "When Did Books Get Page Numbers—and Are They Even Useful Anymore?", Slate, 2005.
— StackExchange: Why do we use Roman numerals for some page numbers but Arabic ones for others?
— Margaret McFadden Smith: "Printed foliation: forerunner to printed page-numbers?", Gutenberg-Jahrbuch Vol 63, 1988, p54–70.
— Paul Lehmann: "Blätter, Seiten, Spalten, Zeilen", Harrassowitz, 1936.
— Bonnie Mak: "How the Page Matters", Studies in Book and Print Culture, University of Toronto Press, 2011. (extract, PDF)
— Ian Gadd "The History of the Book in the West: 1455–1700", Volume II, Routledge: London, 2010. (gbooks)