If you look at the meaning of the word “early” there are several senses.

• One sense is “At a time in advance of the usual or expected event.” e.g. if someone suffered an “early death.” Another sense of the word is “Arriving a time before expected; sooner than on time.” e.g. “you arrived early today!” You’re right that in these two senses of the word, “early voting” sounds weird.
• But there’s another sense of the word early: “Near the start or beginning.” e.g. “Shakespeare’s early works”. There’s also “Near the start of the day.” as in “It’s too early for this sort of thing. I’m not awake yet.” Another sense is “Having begun to occur; in its early stages.” e.g. “an early cancer”. In these senses of the word, “early voting” sounds a lot better.
• For more info see: en.wiktionary.org/wiki/early