It is not necessary to notate pitches or to have names for the notes to observe that melodies have different characteristics and can be grouped by these characteristics.
Neither is it necessary to notate or name pitches to understand that some notes in the scale are closer together and others farther apart. Anyone who played a stringed instrument or built or tuned an organ would be well familiar with that fact.
Music theory is often, if not usually, devised to explain musical practice. For example, the Roman-numeral chord analysis that we learn and apply to Bach chorales did not exist in Bach's day.
Almost anyone can identify, for example, the difference between a melody in a major key and one in a minor key, even without being able to name the difference or to explain what determines the difference, let alone to discuss pitch names or distances between the pitches.
As people sought analytical tools and terminology to communicate about and explain music, they developed understanding that allowed them to explain why these groups of similar melodies were similar.
Thus it is not particularly surprising that the modern theory and practice of notation followed, rather than preceded, the recognition of different classes of melodic organization.