"Over the millennia" is correct English that would be understood. It is just a much less common phrase than "over the centuries."
"Century" is simply a common, familiar word. It's the commonest word we use for long periods of time in human history. We don't commonly say "over the millennia" because we just don't think of history in terms of millennia. We don't usually talk about "the first millennium AD" or "the second millennium BCE." History moves a bit too quickly for that.
The approach and arrival of the year 2000 actually have popularized the word "millennium." Before, say, 1990, it just wasn't a very commonly used word.
When we say "over the centuries," we use the word "the" because we are thinking of each century as an individual period of time with certain characteristics. A phrase like "the nineteenth century" is almost like a name.
If we wanted to indicate a long, vague period of time, in which the unit of time is just being used as a measuring stick, we would probably leave out the definite article. "The landscape does not change much in a year, but it can change a lot over centuries." "Over millennia, small lakes can disappear entirely." "Over eras, mountains appear and disappear."
Similarly, if we were just using "a generation" as a measuring stick for time, we might say "over generations." For example, "Over generations, cultures change and evolve." "Over generations" is in fact a common phrase.
If we are thinking of time as a list of named periods--the Stone Age, the Bronze Age, the Iron Age--then we would probably use the definite article: "Over the ages, we see a tendency for human society to..."