Revision to what i said above: exaggerate a little or much exaggerate make sense as degrees, but over still does not. Again in allusion to the cup of water, something could have spilled over a little or alot but it couldn't "over-overflow".

Many of you are saying that "over" adds "degree" to exaggerate. But to exaggerate means to over do something. So over exaggerate would mean "over-over do". Exaggerate doesn't require degree. Metaphor: you have a cup of water. You can describe the amount by saying it is barely full, kinda full, halfway full etc. But once it overflowed (equal to exaggerate) it's useless to elaborate. It didn't matter if it was a little too much or way too much it still spilled out of the cup. Over exaggerate implies that there is an acceptable amount of exaggeration which defeats the purpose of the word. ALSO under exaggerate makes no sense. How can you not over do something enough. Logically, doing too much is never good. If it was good or necessary you did ENOUGH therefore not exaggerating