It dates from the really early days when Google was basically just a bunch of engineers doing R&D. It was cutesy, the brand they went for was cutesy, it fitted.
The problem with it IMO is that, basically, too many people can't handle it. "Evil" is a really high bar. It's a word that smells objective. But not many business activities really qualify for such a strong word. Drone striking a wedding is evil. When Microsoft tried to take over and then kill off the web (or rather, progress in the web) because they wanted everyone to write Windows apps instead of using open infrastructure, that was roaming around in the general area, maybe, if we want to be hyperbolic. Though it's debatable.
Changing the colour scheme in Gmail is clearly not evil. Attempting to integrate social features of products together is not evil, even if you didn't like it. But unfortunately as Google got big enough it reached the point where basically any change resulted in this motto being thrown back in their face. So it ended up being meaningless. Someone saying "don't be evil" just became some sort of trite cliche. Worse, internally some of its own employees would tend to describe any action they didn't like as "evil" which of course wasn't great for team building and morale (I used to work there so I saw this problem in action many times).
I'm not surprised they have eventually changed it, although even that change will itself be described as evil in a sort of implosion of recursive irony. "Do the right thing" might seem watered down, but by taking out the cartoon emotive character assassination words, it sets a probably more realistic goal by accepting that "the right thing" is inherently subjective and debatable.