First recall how paper is made: You mash up fibers in water, gather them in a mould that's basically a two-piece wooden frame with wires at the bottom, and press the water out and dry them. Frames were of course not single-use items; they were in use for years and the same frame would no doubt make many thousands of sheets of paper. So there's already a standard of sorts in the size of the mould.

Also, from earliest on, that mould size would determine the size of smaller sizes, since the smaller ones were produced by folding the big sheet, particularly with book printing, giving book sizes that remain in use to this day: Sheets were folded into quires. A sheet folded once gave a bifolium, and book with that page format is a 'folio'. ('folio' also means 'page' as in a physical page, with a front and back or recto and verso, making for two pages of text) The paper folded twice gave four sheets in a quire making a quarto (abbreviated 4^(o)) and folded three times gave an eight-sheet octavo (8^(o)). In bookbinding the quires are stitched together to make up the book, and the edges cut later. (and books with uncut pages were sold well into the 20th century, maybe even to this day in some places)

Anyway, as soon as papermaking became common in Europe in the Middle Ages, it became important to standardize the mould sizes among different paper makers. Not, as one might think, for the sake of the printing press (which hadn't been invented yet) but for the sake of trade. So that people could pay a certain amount for a certain paper size, knowing they were getting the exact size they expected. So it was standardized, usually at a local or regional level, as was the case for the plethora of proprietary measurements the medieval world had. There were specific units of measurement for cloth, for beer, for hay, for gold, etc and paper was no exception.

In Bologna, the local paper mould sizes were standardized and displayed publcly on a stone tablet around 1389, on the market square. The text says "These are the moulds of the city of Bologna, which say what the sizes of the sheets of cotton paper must be, which are made in Bologna and the surrounding area, as is set out here below". It was originally displayed at Piazza Maggiore, but is now housed at Museo Civico Medievale (which is however likely a 17th century copy and not the original). It specifies the sizes Imperialle (Imperial), Realle (Royal), Meçane_ (Median) and Reçute (Chancery).

This is not to say that was the first standard, even in Bologna though. Rather just the first legislation of what'd likely been the status quo there. An interesting thing is the proportions here, which vary from 1:1.38 to 1:1.45, which are all very close to the 1:√2 or 1:1.414.. proportions necessary to preserve the paper size proportions when folding the paper, which is used in the ISO paper sizes (A4 etc) that most of the world use today.

In any case, Bologna is not special but representative; both in having its own sizes, and also in displaying units like this on public squares. (e.g. here are the standard brick sizes of Assisi. Or the measurements at Greenwich, for a more recent example) People could settle arguments then and there by going up and checking against the official units. So anyhow, paper remained much like inches and pounds and other units in the grand European menagerie of similar-but-incompatible measurements, where each country, or region or town would have their own standard. And even if they adopted the 'same' standard it wouldn't be untypical to choose the same nominal measurements (x by y inches), it'd be different due to one being (say) Paris inches but the other Swedish inches.

The SI/Metric system was intended to fix all that; and also help do away with the niche units thanks to prefixes; beer could be measured in liters (decimeters cubed) while hay could be measured in cubic meters. Niche units are still around (to an extent I find annoying) though, such as cords of firewood and gold being measured in Troy ounces. The French Academy of Sciences fully intended a unit of paper sizes, as one was suggested by the great mathematician, politician, general and military engineer Lazare Carnot. (whom I admire to the extent I've got a first edition of one of his math treatises; ironically it's in an oddly-shaped quarto) Carnot's suggestion was to use the 1:√2 ratio, and base it on a sheet that was one square meter (which, if you do the arithmetic, means a 841 × 1189 mm page). However, like a lot of the early ideas with the metric system, it did not catch on before falling into obscurity. The 19th century saw the widespread adoption of national standards on, well, just about everything, so paper became more standardized but not at the international level.

The idea was brought back as late as the 1920s by the German mathematician and physicist Walter Porstmann, who developed the A0,A1, .. and B and C-series of paper sizes based off the 1 m^2 base size and 1:√2 ratio for the German DIN 476 standard, finished in 1922 and introduced in 1923. This quickly caught on in Europe and became an ISO standard in 1975. Unusually enough for a metric-based unit, the United Kingdom was relatively quick and adopted it in 1959 (perhaps the fact that it wasn't invented by the French helped; the French themselves were slower, only adopting it in 1967) The rest of the Anglosphere reacted more in-line with their skepticism of SI units, so the United States and Canada do not use ISO paper sizes but rather national ones based off inches (i.e. US Letter).

So, to summarize: The sizes of smaller pieces of paper are ultimately based off the folding of the large sheets of paper the moulds produced. The mould sizes, in turn, was standardized early on to facilitate trade, but weren't more standardized than other stuff, and the move to national and then international standards happened largely in parallel with that movement in other areas in the 19th and 20th centuries. And still isn't totally complete.