The evolution of language is an inherently human process. Words are coined to mean one thing, but can change based on various cultural factors, including geographic, demographic, financial, and of course historical.
For example, there is a verb used in political discussions, "to table". Common usage: "The bill to increase the police budget was tabled". What's odd is that this word means two different things depending on which side of the pond you're on: in America, the term is shorthand for "to lay on the table"; that is, to dismiss from or halt discussion. However, in Britain, the term is shorthand for "to bring to the table", that is, to introduce for discussion". Thus, "tabling" a bill is the start of the process in Britain, but a bad end in America.
This illustrates just one way the same word can evolve to have two different meanings; the shortening of phrases with opposite meanings to the same word or term. These two meanings can then coincide in the same culture if users of the two meanings become culturally commingled.
More to your case in point, let's take the word "cleave". In modern usage, the word has the connotation of a split. However, the word's original meaning is closer to "to penetrate into". Consider an axe splitting wood. The act of "cleaving" the wood happens as the axe enters into the log. If the axe continues all the way through, the log is "cleft in twain"; split in two, hence that connotation. However, if it doesn't, the log is still cleft, but as anyone who's chopped firewood before knows, an axe buried halfway into a log is difficult to remove. A similar connotation evolves from the obvious sexual underpinnings of the biblical phrase "to cleave to one another [and become one flesh]"; the "penetration" causes a bond between the two people, making them one (in many ways). So, the actual historical meaning of "cleave" thus can result in two different colloquial meanings depending on the pictured result.
As far as "egregious", I'm not sure that qualifies. The word has always (as far as Webster's concerned) been synonymous with "extraordinary". This can be good or bad depending on the subject of the adjective. The usual usage is with the connotation that what is egregious is a bad thing: "an egregious series of errors". However, the term can be used positively: "an egregious donation". The synonym to "extraordinary" is obvious if you swap one for the other, and in British English both terms are used as superlatives in both directions, good and bad. In American English, "extraordinary" is normally used to emphasize good, while "egregious" emphasizes bad.