Mr. Mxyzptlk is a great character because he effectively inverts the entire Superman storytelling model.
Superman stories are in many ways about God. Superman can be capricious (as he often was with his tricks in the Silver Age). Superman can be merciful. Superman can be compassionate. Of course, the Superman-as-God metaphor has been stretched awfully thin at this point so I won’t go into further detail on that score, but you get the point: most Superman stories are about a being more powerful than humanity ever can be.
And then Mxyzptlk comes along and now Superman isn’t squat. This is because while Superman is a dandy metaphor for God, Mxyzptlk, for all practical intents and purposes, is God. Mxyzptlk can’t be beaten, stopped or destroyed; he only goes away when you satisfy the rule he made up on a whim. And, like God, he’s basically unknowable; you can see aspects of Mxyzptlk but never the whole.
"Who's Who", Mightygodking.com
246: David, who is the most evil cartoon character ever created? It was before 2000, a long time before.
David: Well, I’m guessing it would have to be someone who is doing or did something really bad.
David: One of those people who destroyed the earth? Or tried to, like Marvin the Martian.
246: We’re not on earth, so that wouldn’t affect us.
David: Someone who destroyed, or would have destroyed something.
246: You’re getting warmer.
David: Everything. Someone who destroyed, or could have destroyed the universe.
246: Uh huh, and who might that be?
David: Damn, this seems so familiar. Oh shit. It just hit me. I wouldn’t have thought of it otherwise. You think backward, as you say, so it wouldn’t be someone really vicious, it would be someone cute. And I can only think of one character that fits those qualifications.
246: And whom do you get?
David: The Great Gazoo from The Flintstones.
David: He got sent to earth as punishment for creating a machine that could annihilate the entire universe.
246: You got it.
David: Sure. But I don’t understand why you consider him the most evil cartoon character.
246: You pointed it out exactly. Because the character of The Great Gazoo is cute. He looks harmless. Hidden evil is much worse and more dangerous than obvious evil. Now, I might have given him a pass on being ‘evil’ except that he knew what his device would do and he knew what the consequences of his actions were.