The minions of Overlord were created specifically to evoke this trope. They look like goblins or the Gremlins, but act like Ax-Crazy little children, loyal to a fault to their overlord and eager to earn his praise. Watching them run back to give you some of the loot they found is adorable. Or watching them grab an item (such as a pumpkin or a dead rat) and use it as equipment (in this case, a hat).
Even more so in Overlord II when they sing and say adorable stuff to their mounts.
Paramites are vicious spider-like creatures with a hand for a face. Strangely, they look oddly adorable.
The Arachnotrons (and possibly the Spiderdemons) from Doom. Also, related to the beholder example: the Pain Elementals and Cacodemons. (The latter actually has had two fanmade plush dolls made, one of them being the official mascot of the DoomWiki.)
The viruses of Dr. Mario are Ugly Cute, even if they are little disease-spreading creeps.
Quite a few of the animals in Star Wars: The Old Republic both hostile and otherwise. A good example would be the Empire Balmoraa World Boss, which is an Ancient Bormu. Bormu are like Hippo-Caterpillars.
Many of the mushroom people in Mushroom Men, especially the hero, Pax. Sure, he's got beady little eyes, a raggedy-looking "lost boy" style tunic, and his mushroom cap breaks away to reveal his brain... But just watch the intro, where poor little Pax is wandering all by himself in the big scary human world, glowing eyes looking out innocently.
The creatures of Jade Cocoon 2 quickly grow on you.
Kouri in Brass Restoration finds the Ill-pin stuffed... characters adorable. They are based on viruses. Ryo, the main character, just doesn't see it.
A lot of Pokémon are this. Even more so in X/Y, where the Pokemon Amie feature lets you play with your Pokemon and brings out the cuteness of a lot of species that most wouldn't think of as being cute at a first glance.
One that comes to mind is Gible. Seriously, just look at it!◊
Especially Snubull◊ and Granbull◊, two bulldog-based Pokémon that are said to be popular with women. In the anime, one even started acting like a Clingy Jealous Girl with Meowth (or was just obsessed with biting his tail).
Some of the Pokémon in the Ruby ROM hack, Pokémon Quartz, fall under this as well, surprisingly.
Feebas◊, a shabby little fish Pokémon, has a secret: if you feed it many, many Dry-flavoured (blue) Pokéblocks and level it up, it turns into something that is Beautiful All Along, the much-coveted Milotic.
Scraggy◊ also counts, since it's a lizard who wears its shed skin as pants. And it's ridiculously lovable.
There's also Muk. He's a giant pile of toxic waste, but comes across as a fairly lovable blob.
There's also the baby Bug-type Pokémon. Most of them are based on squirming larvae that in real life you'd hit with a broom, thinking that an Eldritch Abomination was here to feed on your soul. But Game Freak managed to make them cute.
Joltik◊ - it doesn't help that it's based on the jumping spider.
You probably wouldn't expect a Pokemon based on volcanic remains to be utterly adorable, but Heatran certainly fits the bill. With its derpy, bulldog-like face, its surprisingly high-pitched cry, and the fact that it can be either male or female (and is the only legendary thus far that is able to), it's hard not to fall in love with the cute, melty lava guy.
Most characters from Yume Nikki are really creepy when you first see them, but when you get used to them, some of 'em are kind of... adorable. Like Uboa. Happiest-looking Eldritch Abomination ever.
And Masada seems to be a strange sort of Mr. Fanservice, judging by parts of the fandom, and is also often seen as a Woobie.
If you search on Deviant ART, it's easy enough to find quite a few pictures of fan-made Uboa plushies. Yes, that's right, people like to cuddle with Uboa.
Little Monoko, aka the cutest freak of nature you've ever seen.
Blanka in Street Fighter appears frightening and intimidating at first glance (and don't be mistaken: if you're a bad guy, he is), what with being a muscle-bound green-skinned beast man and all, but deep down he's just a sweet guy who loves his mom and his friends Dan and Sakura. Just look at him hugging his mother in his ending in all iterations of Street Fighter II.
Behold, Gory, the Abomination. A giant golem made of rotted flesh and organs with bone and metal sticking out of him and an stomach that hangs open and exposes his innards...who only wants to be a farmer and tells you so with an innocent, childlike enthusiasm.
Rayman's Raving Rabbids. As well as Moskito from the first Rayman game.
Many of the Zerg creatures from the original StarCraft fit this trope. The little Zerglings are quite cute on the screen, and way they pounce on the Terrans like kittens at a ball of yarn only makes them cuter. All of the wild creatures also apply, being horribly proportioned beasts that look cute in spite of it.
Banelings. Bloated little monstrosities, with the entire back two-thirds of their body devoted to a bunch of pulsating sacs of acidic pus. Before the speed upgrade is evolved, they get around via an ungainly waddle; after the speed upgrade, they tuck themselves into balls and roll around. Their fate is to run or roll into a mass of infantry and explode. They're adorable.
Remember the Ragnasaur found on Char? Big forlorn orange eyes, irritated groan whenever you poke it...
The Colossi from Shadow of the Colossus. Some of them are hard to kill just because they look so cute and pathetic.
The grunts from Halo. After awhile you just feel sorry for them, while admiring their pluck, and smiling at their little dog-like huffs and growls.
Another Halo example are the Engineers. They are essentially floating gas bladders with a small head and tenticles, but they coo like small whales and shiver and recoil in fear from danger. They aren't the most attractive creatures but they are the only passive enemies in the series and eventually you will start to feel bad for killing them.
The alien spawn from The Sims 2 tend to turn out this way. Some players might disagree (and there are hacks out there to have the aliens be more conventionally cute) but the bug-eyed, no nosed green babies are adorable.
The products of "Breed Ugly Sims" challenge games frequently end up in Hollywood Homely territory, being strange-looking but still very attractive (largely due to averting Only Six Faces). The truly ugly ones, however, are inevitably this trope, and consequently no less popular.
In Monster Hunter, there's a small Wyvern called the Yian Kut-Ku. It has an oversized head, disproportionate ears, and is generally very much non cute◊. However, perhaps due to its clumsy running and falling down, his cheerful screechings and his beak feeling similar to a smiling face when open, there are few players who haven't ended up feeling some kind of odd fondness for the guy, and he's a prime target of fanart.
Similarly, the monster Khezu may look like a cross between an oversized maggot and male genitalia, but that doesn't stop fanartists to draw adorable little chibi versions of it. It doesn't help that some of the cutest female armor sets in the game are made of Khezu material.
Almost all of the monsters in general could fall under this category. Moreso when they're sleeping, and especially with their Super-Deformed versions that show up in the Felyne spin-off titles.
The Mini Uragaan in Monster Hunter Tri and Ultimate has gained special fondness from players because of this. And its unique, cheerful battle theme, too.
Sonic Adventure has Chaos, who is fought in multiple forms over the course of the game. A few of the forms can count as examples of this trope, but the best example is probably Chaos 6.
Some breeds of the Chao are also like this.
Another example from Sonic are the alien slugs in Shadow the Hedgehog. Antennae, a single eye, a goopy slug body. Some fans insist they're adorable; others find them disgusting.
Eggman himself, as well as Froggy and Motobug.
In Fallout 3, the bartender of Moriarty's Saloon, Gob.
His mother Carol, too. Despite being what are essentially sentient zombies, they're just so sweet and endearing!
Many Final Fantasy monsters may qualify, but the Tonberry most of all; he may be one of the most dangerous random encounters around, but a diminutive fish-lizard-thing with a lantern somehow winds up being cute enough to sell plush toys.
The Ground Urchins and Raptor Elks from Brutal Legend. Also the Metal Beasts - giant Aztec panther Nibblers.
The headcrabs in Half-Life. Illustrated with Lamarr◊, the pet headcrab of Doctor Kleiner, who while de-beaked and harmless, will nonetheless try to swallow your skull. Valve even makes plushes of them, though the original version was decidedly cuter and less accurate than the current model.
The spore launcher weapon from Opposing Force also counts. It's an infant version of the shock trooper enemies, and is basically a giant alien tadpole. What makes it cute though, is the fact that you reload it by hand-feeding it as it eagerly chomps down the ammo you give it. One of its idle animations has Adrian Shepherd pat it as it happily pushes its head into your stroking palm.
The title character of The Maw. It's an Extreme OmnivoreMiracle-Gro Monster with rows of sharp teeth and one eye. As it grows bigger it's happy chuckling become sinister-sounding laughter. Despite it all it's a cowardly creature who follows the alien player character Frank around like a little puppy and is always happy to eat, and the hug between Frank and Maw's massive eyeball at the end is utterly d'awww-inducing. Think of A Boy and His Blob if The Blob was an Eldritch Abomination.
Megalo from Fossil Fighters. It was deliberately designed to look like people thought dinosaurs used to look, so it's big, lumpy, gray, and dopey-faced. But it's that derpy expression that makes it so incredibly endearing.
The Ettins and Grendels from the Creatures series. The main Creatures, the Norns, are supposed to be cute. But the Ettins have lumpy, monkey-like bodies and strange red eyes, while the Grendels are nasty little reptilian critters with diseases and angry expressions. But when they display the same sort of helplessness as the Norns, well, it's hard not to love them.
Grorns too, with some of the adorable features of norns and the not so adorable features of grendels, are generally adorable anyway.
Hellgate: London had pets, originally available to multiplayer subscribers only, that were intended this trope, and some players find them this way.
Urz, a tame varren (a.k.a. "fishdog") in Mass Effect 2. Unlike most of his species, Urz will allow you to pet him, and if you feed him some pyjak meat, he will happily follow you around Tuchanka, bounding like a puppy.
Thane manages to look like a rotting fish with the voice of a rusty lawn mower and still being a highly attractive man. Of course, Thane was deliberately designed to be exotically alien but attractive to female players.
Garrus is a much better example of this trope, especially after his scarring, considering female Shepard can engage in some good-natured teasing of him for being ugly (which doesn't stop you from being able to romance him). He's also considered The Woobie both in-game and in the fandom.
Silent Hill has the Larval Stalkers in the first game, which have no face and are almost entirely invisible. Harry will still aim his gun at them or hold his Pipe at them, and Silent Hill is one of the few games to still follow the "if it moves, kill it" rule. Naturally you just aim and empty a clip into whatever you're aiming at, but the radio still gives off static. Some people stopped in their tracks simply to watch the little child-like manifestation bumble around and fall over a few times, before finally disappearing.
Nugs look like the subterranean hybrid of rabbits and pigs. Although they're a tasty delicacy to the dwarves, some people apparently domesticate them; in fact, you can acquire a nug for Leliana, which she will name Schmooples. They are actually kind of cute, though their constant squeaking is a bit annoying to the point that Oghren will threaten to eat Schmooples.
Deepstalkers are also cute despite their horrible lamphrey-like mouths and their tendency to spit poison.
Ghasts from Dragon Age II seem to have been designed with this trope in mind. They're vile little gremlins with More Teeth than the Osmond Family, but they tumble out of their holes when they attack, make goofy noises during combat and wear funny hats. They even flop over in a comical way when they die.
So many of the infected in Left 4 Dead fall under this category. The hunter falls under this especially when drawn in chibi style. The boomer looks like a chubby kid with bloated puss sacks and looks like he wants a cookie, the smoker even with his facial deformities, the tank with his humungous body and tiny head, and especially the witch whos basically a zombified Cute Monster Girl. Valve knows the creatures they made are cute. They even made plushies!
In some lights, Left 4 Dead 2's charger and jockey, especially because one looks like deformed hillbilly farmer and the other looks like a retarded midget on crack.
Minecraft's Creepers. Deformed pig model that's green and aptly-named, but is absolutely adorable.
Y'know, when it's not trying to kill your or destroy the creations you've invested hours on.
Within the Monster Rancher universe, the patron saint of this trope is probably the Color Pandora. It is a strange, vaguely caterpillar-esque monster with freaky human faces◊ on its separated body segments... that makes high, squeaky noises and does cute acrobatic tricks. In-universe, it's hailed as a shining example of how to cooperate. Out-of-universe, its Ugly Cuteness gives it a surprising number of fans.
League of Legends features Kog'Maw, a little critter from the Void that spews acidic goo at things. Koggy is adorable in his little mutated way with mannerisms like a puppy, and if official plushies ever hit the merch store Kog'Maw is probably close to the top of the list.
Twitch as well. There's something oddly adorable about the derpy-eyed, crossbow-wielding, plague rat. Might be due to the resemblance to Scratt.
Post-transformation Emil from NieR is a character whose design straddles a surprisingly fine line between being considered vaguely cute and being considered downright horrifying (and for some people succeeds at being both simultaneously). Add in his sunny disposition and penchant for being a bit of a childish romantic and you now have a surprisingly adorable pseudo-mascot... with a grin that will still make people deeply uncomfortable.
The Jinjos, as well as King Jingaling's "cool pet thing."
Some of the Blotlings from Epic Mickey, particularly the Spatters◊ who get a neat little costume depending on what area you're in, and the chubby Spladooshes, who (as long as stay a safe distance or have befriended them) are perfectly content to sit there and sleep.
The Mars People in Metal Slug. Especially in 6, where they salute the player. Awww...
The Dream Eaters in Kingdom Hearts 3D are either this or the standard sort of cute (The Meow Wow being the prime example of the former). If their appearance doesn't get you to find them cute, then their downright adorable reactions to being pet and fed most likely will.
Surprisingly, Painwheel from Skullgirls. Take a look at her without her mask on◊. She also appears maskless in the Story Mode endings of Filia and Valentine. When she smiles, she's creepy and adorable!
A lot of the monsters in the 3D Tales Series games are of this nature if they aren't just standard cute things.
Mujoe (a.k.a. Mr. Meanie) from the Bomberman series.
The Avernum series has the GIFTS, a race of cheerful, childlike ditzes who all talk in squeaky voices and think you're really neat. And happen to be giant spiders.
The zombies in Plants vs. Zombies. Wall-eyed, lopsided, with snaggle teeth and endearingly Narm-y voices. They've been very successfully merchandised as a result of this trope, with several sets of plushies and vinyl figures.
Gish has this as its dominant aesthetic. The player and enemy characters have stylized round shapes and big eyes, which makes them oddly charming despite being neither brightly colored nor innocuous-looking.