"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..."

The correct spelling is 'millennium' and it means a period of one thousand years. The word comes from Latin, so the commonly used plural form is 'millennia'. It is quite appropriate to write: '... has changed many times over the millennia'. 'Over the generations' is an imprecise measure of time; it usually refers to humans but it could also refer to animals. In the context of the sentence above, I think 'millennia' is the most appropriate word to use. My remarks relate to British / International English; American English usage may differ.

You mean "correct", not "true". If something is true, it exists in reality. If something is correct, it is without errors. "Over the millennium" is correct, as is "over the millennia" (plural). You can also use "over the generations". You can check these phrases with an online search.