Possibly the earliest example is in Homer's Iliad, when after Achilles kills Hector, he punctures Hector's ankles and uses the holes to attach Hector's corpse to his chariot with Ajax's girdle, and then rides the chariot around the walls of Troy, dragging Hector's body through the dirt.
The end of Mostly Harmless has the entire planet Earth destroyed, in all parallel universes to boot, with all the main characters on it because Douglas Adams was sick of being asked for more sequels. The radio drama has them escape, in the nick of time.
The craziness of Jonathan Teatime in the Hogfather is established with a recounting of him doing this during an assassination mission. He was supposed to kill an elderly noble, and rather than drugging the guy's dog as would be typical, he nails it to a wall, kills two servants who were witnesses, and kills his victim so violently that his head is several feet from his body.
It's a good thing he did the trick with the spoon where you hold it in front of a victim's mouth to check if he's still breathing. Can never be too sure. Hm hm.
Special Discworld mention needs to go to the Piecemaker, which is described as "a siege cross-bow that three men couldn't lift, [Detritus] had converted it to fire a thick sheaf of arrows all at once. Mostly they shattered in the air because of the forces involved, and the target was hit by an expanding cloud of burning splinters. Vimes had banned him from using it on people, but it was a damn good way of getting into buildings. It could open the front door and the back door at the same time. Hence, "If Mr. Safety Catch is not on, Mr. Crossbow is not your friend."
Then there's How to Kille Insects, an absolutely massive tome. If you were going to use the book itself to Kille Insects, as is often implied when the book comes up, that would be overkill, as it's been used to hit someone so hard his helmet collapses and sticks to his head.
Another Terry Pratchett example is the multiple assassination attempts on Dom Sabalos in The Dark Side of the Sun. The first one uses a black hole.
Among other achievements this lovely young girl managed to lead her fireteam into melee with soldiers devoted to Khorn. Later we learn that her squad sustained no casualties.
In The Traitor's Hand, a Chaos Space Marine is noted as having been killed "with satisfying thoroughness" by two krak missiles and a lascannon, each of which is an anti-tank weapon on its own.
It's hard to say if the refinery-cum-fuel-air bomb in Caves of Ice was "overkill" or "just enough kill", given that it was used on Necrons, but its blast wave was felt in orbit.
The Reynard Cycle: In Reynard the Fox, a shapeshifter is slashed, stabbed, struck by an arrow, beheaded, and struck repeatedly by two of the crew before it finally dissolves. Captain Roenel insists on washing it off the deck, just to be sure.
Another example of overkill in the Expanded Universe is Base Delta Zero, a naval protocol dedicated to eliminating all assets of production on a planet. This varies from rendering the planet uninhabitable and for all intents and purposes useless, to outright slagging the crust.
For that matter, the Expanded Universe seems to have a good amount of overkill—the Sun Crusher fires a pulse torpedo into a star to cause it to go supernova, killing the star system at large; the Centerpoint Station does this by firing a pulse blast through hyperspace to hit its target!
Palpatine created the Galaxy Gun which does pretty much the same thing as Centrepoint, except that it fires physical missiles through hyperspace and "merely" destroys planets (or smaller targets; a lower-yield warhead can be used when appropriate). And the Galaxy Gun was destroyed by being rammed by the Superlaser-equipped Eclipse II Super Star Destroyer, so it's a double example of this trope.
On a more personal scale, the New Jedi Order novel Star by Star features both the New Republic and Yuuzhan Vong revealing their newly-developed infantry. The Republic fields YVH "Yuuzhan Vong Hunter"battle droids capable of dueling starfighters and winning, and capable of incredible feats of precision, correctly identifying and gunning down infiltrators in a crowd of humans without harming the civilians; YVH droids commonly go ten-to-one against standard Vong warriors and win. On the other side, the Vong begin deploying voxyn, Jedi-hunting beasts designed and shaped to be the ultimate killing machines, featuring razor-sharp claws and teeth, acid spit, blood that is both acidic and a neurotoxin, a deadly selection of retroviruses that live on their skin and spines, disorienting screeches, and neural-shock attacks. The voxyn ultimately lose, due to Crippling Overspecialization — they're weak against More Dakka.
In the Halo expanded universe human ships ended up carrying salvos of "archer" anti-ship missiles that could decimate a human fleet (one archer could severely damage a destroyer) just to take down the shields of a covenant frigate. Justified that Covenant frigates can withstand tactical nuclear weapons.
Perhaps the ultimate example of this trope in any form of media is found in The Ringworld Throne. Tunesmith, the Night Person Protector, uses the Ringworld's meteor defense to shoot down invading starships. Said defense is an X-Ray laser powered by magnetically-fluorescent solar flares (yes, you read that right), creating a beam with enough width and power to vaporize - not "cause to explode into tiny chunks," but convert from solid into gaseous state - a planet.
Lampshaded in Homeland by R.A. Salvatore. While he and Alton are being swarmed by spiders, Masoj looks down at his crossbow in contemplation and remarks, "Overkill?"
Alton then, of course, drops a fireball at his feet in an attempt to exterminate the spiders. Overkill andKill It with Fire. Two tropes that go hand-in-hand.
Robert A. Heinlein disapproves of this trope. As he has Sergeant Zim from Starship Troopers comment, war is controlled violence, not killing for its own sake, and there are times where it would as foolish to destroy an enemy city with H-bombs as it would be to punish a baby by decapitating it.
The Star Wars Expanded Universe has numerous cases of insane death machines like the Death Star, the Sun Crusher, and the World Devastators. There are also cases of species doing this, such as the Yevetha and Yuuzhan Vong, who are so fanatical they see winning a war as exterminating the enemy race. When the Yevetha and Yuuzhan Vong encounter each other, it's a Curb-Stomp Battle resulting in the near-extinction of the Yevetha.
The Bothans, with the death of Borsk Fey'la and the disintegration of the New Republic, declare Ar'Krai, a form of total war that they have only done twice in their history. It calls for every capable Bothan to lend their maximum effort towards defeating their opponent, killing every last male, female, and child of the species, slag their home planet to dust, and erase them from history. This (unsurprisingly) causes problems down the road, when the successor state of the New Republic negotiates a peace treaty with the Yuuzhan Vong, as there's no provision for rescinding a declaration of Ar'Krai.
The Lensmen love this trope to bits. When you're dealing with a planet, sure, no weapon is too powerful - but a fleet? The enemy's surviving ships (a fairly large number is implied) are huddled into the ideal globular defensive formation, weapons pointed out, shields mutually reinforcing... and the good guys direct several planets into the centre of mass, in addition to multiple planet-sized antimatter bombs. Yes, you read that right. Subverted slightly in that even after all this butchery is done, there are still a few survivors to be finished off.
The devices used to destroy Ploor - not satisfied with ONE planet moving at fifteen times the speed of LIGHT, aimed at the planet, they fix up a second, identical one to fire at Ploor's sun. They then have to finish off the war ASAP because they're aware that they've finally created the universe's only unstoppable weapon, and if they don't beat the Big Bad within DAYS TO WEEKS, he'll duplicate it and they'll be fucked.
Earlier on in the series, the good guys are faced with the problem of how to defeat the enemy fleet. The solution - build hundreds of specialised starships that are either all defence shields (and no weapons or even human crew) or sluggers with all weapons (and no shields) and assemble them into a gigantic cylinder held together by networks of tractor beams and pressors (the opposite of tractors). The cylinder then flies straight down the throat of the enemy fleet's fire, and when the enemy ships enter its mouth a network of pressors drives them into a single file down the axis of the tube, where each faces odds of between eighty and 200 to one when it gets to the sluggers. At the end, A FRACTION OF ONE PER CENT of the non-remote-controlled ships have been lost, while the enemy is too disorganised to continue fighting.
E. E. Smith's earlier Skylark Series ends up with the "Good Guys" destroying two galaxies by teleporting all the stars from one through hyperspace into collision with matching stars in the other.
"Good Guys" is in quotes for a reason. Their goal is to destroy all chlorine-breathing life in the universe.
The best example of this is when, after a Duke of the Red Court of Vampires cheated in a duel against Harry, Ebenezar McCoy pulls an out of use Russian Satellite down out of space onto the villain's mansion. He's also implied to have caused Krakatoa, the Madrid Earthquake, and several other major disasters.
Later, in Changes, the Red King tries to eliminate both Harry and Ebenezar McCoy by killing Harry's daughter in a ritual that will kill everyone who shares her bloodline (McCoy is Harry's grandfather). Had the ritual been carried out successfully, it would've been maximum overkill. As demonstrated when Harry is able to reverse the ritual to instead target everyone of the Red King's bloodline, exterminating every last Red Court vampire on Earth.
Even later, in the novella Aftermath, Karrin Murphy takes on a building full of bad guys. After all is said and done, she empties an entire clip of ammo into the evil wizard and uses yet another to make sure all of the other bad guys are thoroughly dead. But, as she says, when you're fighting the supernatural there's no such thing as overkill.
What does Morgan do when confronted with an Eldritch Abomination? This happened to be back in The Fifties, so he lured it to a nuclear weapon testing ground and leaves it there. On the day of a test. Given how deadly that thing was though, the nuke was only slightly overkill.
There's also Kincaid's solution to killing a bunch of Black Court vampires. Though, from what we've seen of them, we can't really blame him.
"Blow up the building. That works good for vampires. Then soak what's left in gasoline. Set it on fire. Then blow it up again."
In the Iron Druid Chronicles, it is remarked by numerous people that the best way to ensure that a druid stays dead is to thoroughly pulp the body.
There is a collection of short stories set in the Warhammer 40,000 universe that's entitled "Planetkill".
In The Magician's Nephew, Jadis is described as having been Queen of a world that is ruined when the protagonists come upon it. The reason? Her sister wanted the throne. Instead of killing her and being done with it, Jadis finds and uses the Unspeakable Word, with the result that everyone but herself dies.
Granted, as described, the sister had overcome Jadis's armies and captured her (as a prelude to execution) when she used it.
Perry Rhodan: has Arkon Bombs. Thrown on a planet the planet itself transforms into a nuclear weapon.
They have a device called Transform Cannon  that teleports ignited Nukes, Fusion Bombs or even above mentioned Arkon Bombs inside other ships over a distance of million of miles. (Given they are not fitted with >= 5D-Shields. Then they detonate right on the shield perimeter.)
In the Dale Brown novel Act of War, Zakharov sends several squads of men with anti-tank weapons and a helicopter gunship to kill one man. Naturally, when he goes after bigger targets he scales up accordingly. In Executive Intent a Mjolnir/Thor's Hammer orbit-launched kinetic kill vehicle, capable of causing massive casualties on impact with the ground, is fired at a Russian fighter jet, destroying it so thoroughly that it is reduced to so much dust. The Chinese assault on Mogadishu is also brutally thorough: If even a shot of enemy fire is detected from a building, the Chinese do not try to storm the building - they just level the bloody thing. Any gathering of people that might be construed as regrouping enemy units is cut down to the last man even if it is ostensibly civilians trying to recover their dead.
In Enders Game, the M.D. Device, known as the Little Doctor, causes one atom to explode, then spreads to every other atom around it, causing it to explode. Ender uses this to destroy a planet and two entire fleets.
More specifically, it's a field effect of limited range where the atoms within the field detonate and expand the field slightly. It doesn't work on photons though, so any planet-based chain reaction will cease after a short expansion into space, rather than running wild and destroying the entire galaxy.
The Congress's reaction to finding out about the Descolada virus is to send an entire fleet on a 30-year journey to blow up the entire planet, especially since the target is a planet with minimal industry and a population of farmers in the hundreds and the fact that a single ship with the Little Doctor is enough.
Kelsier of the Mistborn trilogy certainly has his moments. If you ask him, any member of the nobility, or any one working for a member of the nobility is little better than cannon fodder.
One of the first times the Royal Manticoran Navy effectively fields its new missile pod technology in a fleet action, combined with its new long-range missiles that allow the fleet to start firing missiles long before they get within "normal" combat range, results in the enemy fleet getting obliterated almost before they can get a shot off. The number of missiles number in the tens of thousands, so many that a significant percentage are killed by other missiles as warheads detonate and another large percentage don't hit anything at all as there's only an expanding cloud of vapour instead of a target. The Solarian Navy, who have not been paying attention to this advance, have a fleet similarly obliterated after a skirmish with the Manticorans, and the Haven fleet at the end of Mission of Honor, now allied with Manticore, are confident they will do the same to yet another Sollie fleet.
They do. Well, actually the combined fleets (of Manticore, Haven, and Grayson) do at the Second Battle of Manticore. In the worst Curb-Stomp Battle in human history (in a series which has seen several of them up to that point), with roughly equal numbers (although not quality) of ships the Grand Fleet suffers 11 ships damaged, a few LACs (basically torpedo boats) destroyed, and roughly 2000 dead. The Solarians? Two hundred ninety-six superdreadnoughts destroyed, 1.2 million killed in action and 1.4 million prisoners.
Rand Al'Thor in The Wheel of Time series has used this more than once. A scene in The Gathering Storm is particularly noteworthy: He has finally tracked down Graendal to her castle. She is a noted Chessmaster, and Rand doubts that he can outwit her. So instead, he sends in a pawn, a minor nobleman who's stupid, power-hungry and easily manipulated, as a messenger. She uses Mind Control on the nobleman and sends him back to Rand, treating it as the start of an intricate game of backup plans and countermoves. It turns out that Rand was prepared for that; he detects signs of the Mind Control, takes that as solid confirmation of Graendal's presence, pulls out his biggest Amplifier Artifact, and drops a Magical Nuke on her, erasing the entire castle and everyone in it from existence. It didn't work as well as he hoped, but he still managed to get one Forsaken, albeit not the one he wanted, and at least one Black Ajah, so it fits this trope.
This example, like many other uses of Balefire, seems to actually be a subversion. It appears that it's Overkill at first glance, but sometimes it's the only way to be sure. Showing restraint and simply killing the Forsaken through other means has allowed them to be reborn. Also, despite being called Overkill, this particular example with Graendal turned out to be not enough kill as mentioned.
In The Merchant Princes Series, a Cycle of Revenge quickly becomes this. When knowledge of the Clan, a dimension-traveling group of smugglers, comes to the attention of the government, President Evil tries to Nuke 'em because of the potential security risk they represent. Well, that's the pretext, at least. And his bomb succeeds only in hitting one castle, occupied mostly by an enemy of theirs at the time. However, a conservative faction of the Clan decides to retaliate by setting off three nuclear weapons in Washington, DC. They succeed. In retaliation, President Evil's successor sends dimension-traveling ships to the Clan's home country, an area roughly the size of Massachusetts, and carpet-bombs them with nuclear weapons. It's called, appropriately, CARTHAGE, and probably would have caused nuclear winter on that world.
In the Bolo novels, the 'Final War' against the Melconian Empire ended like this. The Terran Concordiat declared that every single planet in the Empire be completely cleansed of life. The Melconians made a similar declaration against the Concordiat at about the same time. Both succeeded. The war ended with both nations reduced to a few scattered remnants desperately searching for a planet that could still support life. Since the fragments of the Concordiat were slightly larger, they can arguably claim victory.
Firestar's death in The Last Hope. Loses enough blood to fill a pool, then has a flaming tree dropped on him.
In the first series, Swiftpaw is literally ripped to pieces by dogs.
One of the Man-Kzin Wars collections contains the story of a ship called Catskinner, which is a crewed ramscoop ship that has a largish number of 500-pound chunks of iron that it drops shortly before reaching its target system. It slows down by hitting the star. For those lacking a grasp of the scale, the effect is like a relativistic shotgun blast the size of an entire star system. This was the diversion for the real mission, which was to insert (two teams of) assassins to kill the recently arrived representative of the Kzinti central government before he could mount a successful invasion of Earth. This manages to be both overkill (for a diversion) and under-kill given what they could have done to the system...
The same universe also has the weapon called the Wunderland Treatymaker. It's a disintegration cannon that was used on a Kzinti base. The human name for the world is Canyon, due to the kilometers deep chasm the size of Baja California that was gouged in the surface.
In Mr Blank, the Templar Eric Caldwell was shot twice in the chest with a .12 gauge, thrown through a plate glass window, run over, and set on fire.
Lampshaded in How to Seize a Dragon's Jewel. The witch and Alvin have literally every single one of their thousand warriors aiming their spears, swords, bows, axes, and rocket launchers right at Hiccup. Justified in that he has escaped from impossible situations before, and sure enough, Hiccup manages to vanish right before their eyes, by being kidnapped by an invisible dragon.
Black Tide Rising: In general this is the attitude of those clearing the zombies, but in Strands of Sorrow during one attack against a horde using 40mm grenades fired from Amtracks, at targets within the Arbitrary Minimum Range of the grenades, it's mentioned that there is such a thing as "overkill".