This seems to be a fairly standard cultural trope - not that people with mustaches are generally portrayed as sinister, but that sinister characters are frequently depicted with mustaches - and I’m wondering where it came from. I think it predates Hitler and Stalin.
I suspect that it dates to a time when certain nationalities or ethnic groups which favored mustaches (Italians?) tended to be portrayed as villains, and the mustache got the connotation by association and/or was used to summon up this stereotype.
If you are a Salafist and/or Wahhabi Muslim, or some types of German origin Christians, then Mustaches are evil personified.
They are supposed to be a sign of martial endeavour and not to be countenanced by peaceful types.
Quite why many insurgent videos of killings from Syria feature murderers with shaven upper lips escapes me. Not to mention the large number engaged in firing all sorts of ordnance and engaging other anti-social activity.
The Amish also avoid mustaches when they grow beards. According to this it is because in the early days (1600s-ish?) military men sported elaborate mustaches, and the Amish and their predecessors were trying to be conspicuously “not them”.
Exaggerated moustaches were part of themasks of the stock Commedia Del’Arte characters known as Il Vecchi (old men) and they’re most often the antagonists in the plays. Pretty much the forerunners of the Snidely Whiplash archetype, especially in some of the darker plays.
It’s hard to trace, but my guess is that the modern image of the mustache-twirling villain comes from Victorian stage melodramas, both English and American. They may have descended from Commedia Del’Arte, since so much did, but it would easily be independently reinvented. The stage in those days used exaggerated makeup to ensure that even the most distant seats could follow along. A mustache was a great way to tag the villain and give him “business” - the twirling or tugging or other bits of action to emphasize or supplement words. Mustaches, like masks, were easy props to put on and take off so that one actor could play multiple roles in small companies.
Wikipedia says that the handlebar mustache is also called a spaghetti mustache because it was a style associated with Italians. No time line is given, though. The Italian mustache may have garnered sinister connotations because it matched an already existing trope.