the Nazis believed many things considered insane even by the average Joe's lowly standards, like "mass-murder is a good thing".

I'm not sure they considered it a good thing, maybe they would have preferred to just ship off all the Jews to Madagascar, the Final Solution was a second-best solution that happened to be cheaper and more practical.

And the "average Joe" you're talking about would have to be a Western one - I suspect in many countries, mass murder of some ethnic groups wouldn't be considered insane by everybody's standards, especially in a war situation - either because they're sitting on some land that's "rightfully ours", or they're more economically successful, or they're not-very-well integrated immigrants, etc.

By the way, Hitler isn't always seen as a Big Bad Guy by the non-Western world, sometimes he's just considered a pretty bad-ass leader like Stalin or Napoleon. When a german friend of mine met her new colleagues at a Chinese univiersity's biology lab, one of them said "Oh, you're German! Like Hitler! Cool! thumbs up". And the Chinese find that the Westerners don't seem that aware of how nasty the Japanese were.