The Inca might have been the largest non-literate society in history. Allow me to explain by way of two definitional digressions.
Any society has peripheral or marginal members that are less in tune. We won't know quite where to draw the line, and of course the population data we have is worse than incomplete. More so, the concept of society that we all live with, and the culture and institutions that make it up, are strongly tied to writing. Today, written communications are always used for planning, because they are persistent and carry much higher bandwidth than spoken language. The administrative capacity of a society organizing itself on the basis of spoken language and pictographs is so much less that these "political units" may have had pretty fuzzy edges.
So what qualifies as writing? I'm guessing you don't think pictographs do; all their explanations are visual. On this basis we rule out cave paintings and so on. However, the boundary between proto-writing and writing proper is loose. Pictographic systems gradually acquired the phonetic properties that allowed them to record whole phrases with embedded subclauses, such as incorporating the rebus. The gold standard is a universal medium that can represent any phrase, arranging symbols in a specific order so that a reader can recite them back intact. Let us review the principal indigenous American encodings:
Incan quipu are definitely a means of storing information. Despite centuries of analysis and millions of people still speaking Quechua, though, they have not been shown to encode phrases of language. Noone knows how to represent a story or a command in quipu form. For that reason, for now, they are considered a medium of accounting or proto-writing. The Incan empire has been estimated as exceeding 10M inhabitants.
Aztec codices are more representational and better understood than the quipus. Still, and despite millions of contemporary speakers of Nahuatl, Aztec writing has not been shown to represent specific language phrases. It has some phonetic components, but not in any order, so it is not a unified system for encoding the spoken language. This is why none of the codices preserve songs or epics and why Neo-Aztecan Mexican nationalists have not been able to publish any new works in the Aztec script. It does consist of symbols marked onto a flat sheet, but is only proto-writing. The Aztec empire might have been half the size of the Incan one.
Mayan glyphic inscriptions are more advanced. While they are not wholly understood, and use both phonetic and representational elements, these do occur in order, encoding whole phrases, and can be transcribed. Mayan writing is therefore a proper written language.