In Dead or Alive, Hitomi and Mila are easily the best examples of the trope, with the former being a hardhitting Karateka, whose kicks and punches send her opponents flying across the arena. While Mila is a MMA fighter that looks and fights just like real life cute bruiser Gina Carano.
May from Guilty Gear, a cute little pirate girl who fights with an anchor as big as she is.
Presea Combatir from Tales of Symphonia, who was originally a lumberjack and wields a massive axe. She is the cutest character, bar none. At one point she is able to drag a heavy wooden log single-handed, a feat which neither Genis nor Lloyd can do together. This leads to Lloyd declaring that "I've lost all confidence as a man". She's a rare case in which the shortest character in the party is also the resident Mighty Glacier.
In another cutscene, the frail-looking Colette lifts Regal with one hand after Zelos couldn't lift him. This leads Raine to call all men useless.
And before that, when the party first meets Zelos, she grabs him and throws him with one arm when he approaches her with lecherous intent. Granted, she had lost her soul and heart at that point and could not control herself, but wow.
Hermana Larmo of Tales of Innocence is a fist fighter, although she focuses more on speed and multiple strikes than sheer damage like Presea. Far from emotionless, though - she apparently teaches other superpowered young children clandestinely in the sewers, and tends to draw out the last syllable of her sentences (and attack names) into a "yan". Also, she's the reincarnated form of the divine dragon Vritra, whose form she can take in her Awakening Hi-Ougi.
Karol Capel of Tales of Vesperia is the youngest member of Brave Vesperia (A guild he leads) Goes into battle wielding a Battle Axe while still dressed in his little overalls. He gets his moment in the Blade Drifts of Zopheir when he single-handedly fights a boss until he's disarmed, then grabs a nearby weapon and performs a backflip-attack.
This is further emphasized in the coliseum (in the PS3 version, a "Merciless" rank is available in the coliseum for team battles - at the end you fight the party members you didn't bring in with you), where Karol is so damaging that he's one of the highest profile targets after Estelle, who is capable of some spectacular magic spells and can heal and raise the dead.
Hinako Shijo from The King of Fighters makes a rather amusing sumo wrestler, especially given the fact that she weighs just over forty kilograms (88 pounds).
Team Psycho Soldier has had a few cute bruisers on its roster in the later games. 2001 saw Bao, cute little boy and powerful psychic (and, to many fans, The Scrappy). XI replaces him with Momoko, a cute little Genki Girl that can perform ridiculously long attack chains.
Apricot Sakuraba from Galaxy Angel II. She also has a very strong case of androphobia, so whenever a man touches her, she involuntarily screams and flings him into the air.
Marcy of Chrono Cross is a tiny little girl in a frilly pink dress... and probably the toughest one of General Viper's elite, which includes a man about as big and strong as an elephant. Most of her moves involve beating you three ways to yesterday with yarn. Among playable characters, Leah, who despite being a child has great strength and HP; she is, in fact, basically a kid version of Ayla from Chrono Trigger and is in fact implied to be Ayla's time traveling mother.
Prolific in World of Warcraft, thanks to Purely Aesthetic Gender and the lack of substantial stat differences between races. You're just as likely to be beaten senseless by a two-foot tall gnome girl with pink pigtails as you are by a nine-foot minotaur warrior with a weapon larger than you are. Sometimes more likely, since the Gnomes are harder to click on in a crowded battlefield where tab-targeting is impractical.
This trope is inverted for male Draenei Priests/Mages, male Orc Warlocks/Mages, and male Tauren Priests.
Even more so in City of Heroes, with not only Purely Aesthetic Gender but Purely Aesthetic Appearance, period. A cute teenage girl can have the exact same powers as a hulking brute or musclebound, grizzled warrior, hero or villain. In-game examples include Mynx, a deadly Cat Girl and Fusionette, a reckless and bubbly Glass Cannon.
This is made even more extreme by the fact that the size scale can be adjusted from 12 feet tall to a mere 3 feet in height. Tiny heroes able to floor giant men made of rock, or withstand constant barrages of machine gun fire are so popular that the game picked up a fan-term for them: Microheroes.
Mazzy Fentan of Baldur's Gate II is a halfling paladin in an edition that doesn't let halflings be paladins. Statistically she's a fighter with some extra spells, but the behavior is all there. Voiced by Jennifer Hale, she manages to be tiny and adorable yet classy and honorable at the same time. Oh, and more or less a living buzzsaw through the forces of evil.
Alena, the Rebellious Princess from Dragon Quest IV. While she's very limited in what weapons and armor she can use, Alena's physical strength and critical hit rate are so much higher than the other party members' that it doesn't really matter. Especially once you equip her with a female-exclusive weapon that lets her attack twice per round. She also largely makes up for her limited armor options by having the highest evade rate. Basically, her kung fu is stronger than yours.
Krile from Final Fantasy V can fit this trope, especially if you give her physically oriented jobs. Which, given that she inherits her stats from Galuf, might be the jobs she has leveled up to start with. Her outfits seem designed to be as adorable as possible—for example, her bubblegum-pink Knight armor.
While Relm Arrowny may not be a great physical fighter, many believe she is the most powerful pure mage in Final Fantasy VI. This in stark contrast to her grandfather, the Blue Mage, and half-Esper Terra means that game balance might be Fridge Logic retardant.
In Dissidia 012 Final Fantasy, Prishe is the Token Mini-Moe, a young Bare-Fisted Monk with Frills of Justice and purple hair. Her punch combos, particularly One-Inch Punch and Howling Fist, are incredibly powerful, those two in particular can crush guards and deflecting attacks when charged up, and her ability to link two attacks together gives her impressive power. For example, her Dragon Kick to One Inch Punch link has a base power of 25-35 if both attacks are charged up, making it one of the most powerful combos in the game.
There are a lot of characters in Touhou who could qualify. However, the greatest example would be Suika Ibuki, being barely three feet tall and about as developed as a six-year old... and an Oni with enough muscular power to smash a mountain to pieces between drunken binges.
Another good example is Suwako Moriya, who is not only an EX-Boss, but has the most damaging melee combo of any other character in the fighting spinoff, Hisotensoku.
Cirno is also a prime example. She's treated as relatively weak in-setting, but that's only because Touhou is full of extremely broken characters. From a normal human's (or even a weak youkai's) viewpoint, however, she's perfectly capable of freezing her opponents, the building they are in, and a good chunk of the surroundings while monkeying around. She IS right when she calls herself the strongest Ice Fairy; for her race's standards, she is enormously powerful.
Laharl, Etna, Yukimaru, and just about half of the units of Disgaea. It's not difficult to create an attacking force consisting entirely of BFS-wielding lolitas if you feel the urge to.
She may not have super strength, but Emilia of Yggdra Union otherwise fits the trope perfectly. The younger sister of the Big Bad, she frequently appears at the worst possible times, outdone in this respect only by Aegina and Luciana, and is one of the most difficult recurring bosses in the series... and she's only 14. Granted, the game's art style makes everyone look about 10 years younger than they really are...
Most female weapon-users in the Fire Emblem series are Fragile Speedsters or Archer, but Sacred Stones gave us Amelia, who starts out as a fairly raw recruit but can eventually become a General, Great Knight, or Paladin—or, for maximum application of this trope, take the "Super-Recruit" path, thus doing massive damage (as super-recruits have high Critical Hit rates) with a lance larger than she is.
Jill from Path of Radiance and Radiant Dawn (or not) might also qualify, as she's a member of the mighty Dragon Knight class and, according to a support conversation in Path of Radiance, is about the same age as the Token Mini-MoeWhite Magician Girl Mist.
Meg from Radiant Dawn is yet another possible future General.
Nowi from Fire Emblem Awakening can become one if she class changes into a Wyvern Rider, as she's easily the youngest looking character out of the entire cast, yet potentially just as capable of handling a huge battle axe or lance.
In addition, any of the female children that are born can become a General and/or Dragon Knight as long as either their mother or father had access to the class. Out of the kids themselves, Sully's daughter Kjelle has Knight (the class that predates General) as her starter, and she's a teenage girl who always has her HUGE armor on.
Saki from the Oneechanbara series. She's 16, and looks even younger. She is a fairly solid swordsman... and her alternate combat style is fighting bare-handed and/or using throws, in which case she shows the ability to tear zombies' arms off with her bare hands or suplex them so hard their heads fall off. Yeah.
Speaking of Persona 4, Chie certainly qualifies. An Extremity Extremist that literally kicks her way out of battle, her follow-up attack allows her to turn an enemy, as well as minibosses and even bosses, into A Twinkle in the Sky. On the top of that, Chie gains the powerful physical attack God's Hand, which will bring endless amounts of pain to her adversaries.
This doesn't begin to describe the unmitigated cuteness that Chie represents. Especially at higher levels and with proper equipment, her agility can get very high, to the point where she's quite difficult to hit. The cute part? When she dodges, she goes "Noink!" It doesn't stop being adorable.
And before Chie, there was Persona 2's Lisa Silverman.
Wild Flower in Jade Empire is a nice little girl... except the fact that she's possessed by two demons who are battling for control of her.
MOMO of the Xenosaga series starts the series off as a Magical Girl, but in the second and third games, she becomes a massive bruiser who can deal the most damage out of the rest of the party barring a Game Breaker like Erde Kaiser. Not to mention her version of another party member's attack in Episode III is stronger. And the other party member is the local cyborg.
Ryugu Rena in Gaiden GameHigurashi Daybreak. Her first weapon is her butcher knife and when she's using it she's an uncommon female example of the Jack-of-All-Stats. Her second weapon is an axe which makes her slightly slower but more powerful, as a subdued form of a Mighty Glacier (rare for a girl). Her EX-Weapon is a Cloud-likeBFS that boosts her damage output through the roof and makes her so strong she's a Game Breaker. Subverted by the fact that she's on full-Yandere mode when wielding this weapon, making her significantly less cute than the other, non-Axe Crazy examples.
B(aby) B(onnie) Hood aka Bulleta from Darkstalkers is a little blond girl, wearing a Red Riding Hood outfit. She's actually a bounty hunter that hunts Darkstalkers (especially Werewolves) for money and instead of bread and wine for Grandma, her basket contains machine guns and bombs. Did we mention she's also a Psycho for Hire in the most literal sense imaginable?
To drive the point home, if you are a muscular man that can put The Governator to shame and defeat a whole army of marines, you stand a chance at surviving an encounter with a C-class Darkstalker. A and S-class Darkstalkers (the highest there are) are outright terrified of Bulleta.
Hsien-Ko/Lei-Lei fits this trope as well perfectly. A cute and apparently harmless Chinese zombie girl, she can hold a wholesome set of weapons of all kinds of sizes and shapes in her sleeves. Not to mention she has strength enough to throw a character bigger than her into air.
Gnar, who is also a prehistoric, shapeshifting, feral yordle (and as such is also pint-sized), Nidalee (a  huntress who can transform into an adorable wildcat that has the potential to maul you to death), and Nunu (a yeti-riding, snowball-slinging child) all naturally fit the criteria for this trope. All of the aforementioned champions tend to be on the beefier side of the League champion pool, and can be very blunt and lethal in their combat styles.
In Fable II your hero as a child doesn't nearly match the levels of the other cute bruisers on the list, but he or she still manages to take down a much larger, stronger bully who managed to take down a similarly aged teen (namely Rose, your sister) with a single surprising headbutt. And does it in five short strikes with a wooden sword or a similar number of shots from a spit-shooter.
Talim from Soul Calibur certainly counts. She's the smallest human character, and quite possibly the lightest character. Yet despite her diminutive size of four foot nine, she can easily take down the biggest and baddest of the roster.
Xiaoyu, Lili, and Asuka in Tekken They don't look that imposing at first glance (especially waif-like Xiaoyu), but they have no trouble tossing around the heaviest of foes. Launching a 15-foot-tall demon into the air and flinging around a practically-solid-steel-and-osmium android like a rag doll, anyone?
Actually, almost all of the witches from the Luminous Arc serie are this.
A large number of Pokémon are this. Azumarill stands out, however: an adorable, beach ball-esque rabbit. Whose physical power (thanks to its ability) rivals heavyweight behemoths like Groudon and Zekrom by mere points.
Iris is easily the Token Mini-Moe of the Pokémon Black and White games and anime series. In Pokémon White, she challenges you with a full-fledged party of Dragon Pokémon. In Pokémon Black, she can teach your Dragon Pokémon the most powerful Dragon-type move.
And in Pokémon Black 2 and White 2, she's the champion.
Mew may be the Ur-Example in Pokémon. The exact size of a Pikachu, Mew has base 100 in all of its stats, thus its Average Stat Value is 100. This means it's categorized in the same strength tier as juggernauts like Tyranitar and Dragonite (most other non-Uber legendaries - i.e. Articuno, Zapdos, & Moltres - in the game have an ASV of around 97.7). Add to these stats Mew's ability to learn any and all TM, HM, and nearly all non-unique Move Tutor moves in the game, and it becomes clear that Mew is an adorable god of death.
Pokémon Sun and Moon added Stufful and it's evolution, Bewear. Both are adorable mons based on Red Pandas and stuffed animals (Stufful) and Japanese Mascots (Bewear), but are monstrously strong. In fact, they're Normal/Fighting types to boot, and all of their dex entries mention their massive strength.
Irene from Shining Force III. A tiny woman with girlish pigtails, big doe eyes and a fancy Chinese-style dress, who doesn't speak the local language well for extra vulnerability points. Her method of fighting, in a game where most humanoid characters carry big ol' swords, axes, lances and the like? One oversized boxing glove and her feet. Oh, and she's a monk.
Veronica of Fallout: New Vegas is a cheerful, slightly snarky girl voiced by Felicia Day whose main ambition is owning a dress (and she will Squee! if you give her the right kind). She is also quite capable, with the right tools, of punching the head off of something. And she bubbles with eagerness to do so.
Liara in the Mass Effect series is a sweet, innocent young archaeologist who, at least out of combat, looks like a pretty standard pretty blue alien woman in a labcoat. In combat, she will start glowing blue, breaking peoples' necks by gesturing at them, and summon small-scale black holes to mess with enemy positions.
Not to mention that in the Lair of the Shadow Broker DLC for Mass Effect 2she becomes the new Shadow Broker.
Tali may count as one, too. Though she starts out relatively weak with great tech skills, upgrade her armament to Shotguns and give her the Spectre shotgun and watch her mow through some geth like nothing. And then she takes a level in badass between the first game and the sequel (especially)...
Kasumi, a super thief and Genki Girl, who's always cheerful and full of whimsical comments... and can also drop a gunship all by herself.
Ellie, the protagonist of Monster Tale, is a little girl capable of sending monsters flying across the room and breaking stone... with a satchel.
Milliarde of Baten Kaitos Origins is the sheltered daughter of an Alfard nobleman. She's seventeen years old, wears a cute dress, and has butterfly wings. In battle, she dual wields giant spiked clubs and sounds a little too happy, as well as serving as the party's Mighty Glacier.
Cecille in Suikoden III. Cute as a button teen girl who's shorter than even Thomas (and Thomas is a shrimp, by his own admission). She also patrols Budehuc Castle all day in full plate armor, wielding a spear larger than she is and a buckler, and trains every morning by running two miles in said plate armor. Her exclusive War Horse rune is also one of the most damaging attacks in the game, although it has low accuracy.
This is honestly just about every playable character in Neptunia. Take pity in those who are foolish enough to underestimate them just because of their looks, especially Compa with that giant syringe.
Kingdom Hearts: While it doesn't apply for all of them, most of the Heartless look too cute to be an army of bloodthirsty creatures.
Similar to the above-mentioned problem of selecting gnomes in a huge melee in World of Warcraft, in Fallen Earth short female characters are favored by PVP-focused players because they have the smallest hitboxes, making them just that little bit harder to target.
In Sanctum 2, the explosives expert of the gang is the main characters teenage sister, Sweet. In pigtails, no less.
Tia in Lufia: Curse of the Sinistrals. While the other heroes wield traditional weapons like swords and hammers and have attacks like firing an enemy-piercing beam of energy or conjuring icicles around them, Tia has...a glove that fires out of a luggage case. Which she punches monsters with. Repeatedly. Which nothing in the game can compete against in terms of single-target damage.
Rare male example, Prince Dreambert of Mario & Luigi: Dream Team turns out to be this. We see him take out Mooks at a few points but when you realize how just badass the little pillow guy can be is when he battles Antasma, a fearsome nightmare demon king, to a draw. Later on he ends up on the receiving end of a No-Holds-Barred Beatdown by Antasma but that was only because he used the dream stone to increase his power in the dream world.
Just like the two protagonists, many of the enemies in Head Over Heels are cute.