I personally feel that the term is a redundancy. While I can concede that some may see value in distinguishing higher degrees of exaggeration, the problem is that everyone I hear use the term "over-exaggerate" simply use it in place of "exaggerate" for every instance. It's the same problem that everyone has with "could care less" and "irregardless," or the rampant use of the term "literally." This is what upsets me about the word. There is no thought placed in its usage. It has simply become the new default, at least from my experience.