tl;dr: Hundreds of thousands, but not millions.
Current calculated total: ~152,262 - 343,106.
To begin with, there are a couple of misconceptions here which need to be cleared up first:
The population of the Seven Kingdoms was much higher than half a million.
Jaime did not save the entirety of Westeros (at least not directly), he saved King's Landing, from the Wildfire Plot.
Break-it-down
The War of the Five Kings was a war involving the following "belligerents":
- The King on the Iron Throne: Joffrey Baratheon
- The King in The North and The Trident: Robb Stark
- The King in the Narrow Sea: Stannis Baratheon
- The King in Highgarden: Renly Baratheon
- The King of the Isles and the North: Balon Greyjoy
The war was ignited when Catelyn captured Tyrion on suspicions that Tyrion had attempted to murder the crippled Bran, after his fall.
There were a few battles/clashes within this war, namely:
The War in the Riverlands
A pre-cursor to the Stark vs. Lannister wars. Jaime starts attacking the Riverlands and heads towards Riverrun. This is in retaliation to Tyrion's capture.
Major battles include:
- Gregor the Pillager
Tywin saw the act of Tyrion's capture as a disgrace to his family's honour, so he sent Gregor and his men on a pillaging mission in the Riverlands; all to lure Ned out into the Riverlands where he could then be captured.
- Total deaths: ~100-500 mostly smallfolk and castellans
- Battle in the hills below the Golden Tooth
- Battle at the Mummer's Ford
Ned is injured after his sortie with Jaime at King's Landing, so he sends a small task-force lead by Beric Dondarrion to stop and capture Gregor Clegane, in the name of the King.
- Total deaths: 120 men, including Lord Beric Dondarion1
- Battle under the walls of Riverrun
Jaime pushes forward toward Riverrun
The Wolf and The Lion
This is where it gets interesting. Robb Stark enters the war on behalf of the Tullys, and all hell breaks loose. Note: Robb’s main host is ~20,000 men in total and the Lannister forces are ~35,000.
Major battles include:
- Battle on the Green Fork
- Battle in the Whispering Wood
- Battle of the Camps
- Total deaths: Not many, probably ~1,000
- Long Live The King
King Robert Baratheon decides to go hunting and proceeds to get impaled by a wild boar, causing his death:
- Execution of The Traitor
Cersei Lannister and the City Watch overtake Ned Stark's personal guard and household keep from Winterfell and declare him treasonous. Ned is captured and later executed, his entire household is killed (except for Arya and Sansa):
- Total deaths: ~55 including the five guardsmen which Syrio Forel kills with his wooden sword and the eventual beheading of Ned Stark
- Retreat to Harrenhall, Sack of Darry and Reclaiming of the Riverlands
Tywin's forces retreat to Harrenhall, destroying and pillaging any nearby towns, including raping and murdering the smallfolk.
Robb gets declared King in the North (and the Trident) and his forces reclaim various holdfasts within the Riverlands.
Darry is reclaimed, but is soon retaken by Gregor Clegane who puts the entire Darry household to sword.
- Total deaths: ~5,000 - ~10,000 mostly smallfolk
Rise of The Kraken
Balon Greyjoy decides he wants to be The King of the Isles and the North. In order to establish his claim and solidify his influence, he orders the reavings of the coastlines. Theon decides he wants to be a Greyjoy again and to please his father, hence takes Winterfell.
Battles include:
The Clash of Kings
After a short break, Robb decides to take to the offensive. He sends Cleos Frey to King's Landing with a letter of peace, but secretly attacks.
- Battle of Oxcross
Rob Stark takes Stevron Lannister's army by surprise
- Total deaths: unknown, possibly ~1,000
- Taking of Ashemark
More scouring occurs, this time of the Westerlands. Robb's forces take the Castle of Ashemark and bolster his army with supplies and livestock from nearby towns.
- Total deaths: unknown, not significant
- Siege of Storm's End (299AC)
Stannis besieges Renly's seat, Storm's End (the traditional seat of House Baratheon). Renly parlays with Stannis but fails to come to an agreement and set a time for the fight, for next morning. Renly however is killed that night by Stannis and Melisandre's shadow demon. Loras goes berserk mode and kills Renly's guards, Robar Royce and Emmon Cuy. Stannis moves on to take Storm's End and Ser Cortnay Penrose (castellan of Storm's End) is killed by Melisandre's shadow baby v2.0; Storm's End is surrendered.
- Bitterbridge
Not a battle per se, confusion and anger takes over the 80,000 men strong camp of Renly's with Ser Loras Tyrell still deep into his berserk mode. Lord Randyll Tarly takes over, and true to himself, puts many men (mostly Florents) to death. The army is split, some defect to Stannis' side, some stay with the Tyrells and later join The Crown.
- Total deaths: unknown, let's say ~1,000
- Battle of the Fords
Tywin is angered and decides to take matters into his own hands and marches upon Robb's host in the Westerlands. Edmure Tully hears of this and decides to cut him off. Although the victory went to Edmure with high casualties on the Lannister side, it was later revealed to have been a mistake since Robb wanted Tywin's host to enter further into the Westerlands and be unable to save King's Landing from Stannis' attack. However Tywin was able to retreat and take Stannis' army from behind. Oh, poor Edmure.
- Fall of Harrenhal
Roose's men set upon Harrenhall, which is presently occupied by Amory Lorch and Vargo Hoat (and the Brave Companions).
- Storming of the Crag
This is where Robb gets injured and meets Jeyne Westerling
- Total deaths: very low, perhaps only 1 (killed by Grey Wind)
- Battle of the Blackwater
This one's the big one! Lots of parties, and lots of casualties. Most of Stannis' fleet as well as a majority of The Crown's fleet was nuked to oblivion by Tyrion's infamous wildfire plot.
- Total deaths: countless
- at minimum: 7,283 confirmed
- at maximum: ~94,000
The War Winds Down
After Stannis' defeat at Blackwater and the Ironborn taking castles in The North, including Winterfell, Robb is forced to retreat and protect his homeland.
Major battles include:
The Feasting Crows
The Lannisters think they've assured their victory, however there are still major undercover plots being enacted.
Major events include:
- The Purple Wedding
Admit it, you cheered didn't you?
- Total deaths: 2 (Joffrey and Ser Dontos)
- Trial of Tyrion Lannister
Tyrion gets blamed for the Purple Wedding and is put on trial. He demands a Trial By Battle in which Prince Oberyn Martell volunteers as tribute and the Crown names Ser Gregor Clegane as its Champion. Oberyn promptly decides to get impaled and has his face crushed-in, but not before poisoning The Mountain causing his delayed death.
- Death of Tywin Lannister
After getting jail-broken by his brother Jaime, Tyrion decides he's not going to leave things in peace; he sneaks into his Pa's bed chambers, finds Shae, chokes her and proceeds to conduct a scientific-experiment to determine whether Tywin Lannister truly shits gold. He didn't.
- Attacks of Lady Stoneheart
Lady Stoneheart is created and takes over the Brotherhood Without Banners. Starts wreacking havoc on the Riverlands and gets revenge on Freys and Lannisters like they're tree ornamentss.
- The Battle of Castle Black
This one's another big one. Mance decides that the best place to hide from the oncoming Others is behind the Great Big Magical Ice Wall. However, he thinks the best way to do this is to attack and kill the current residents - the Uber-Emo Night's Watchmen. During his attack though, Stannis The Mannis decides he's having none of it and takes Mance's army from the flanks.
- Total deaths: 2,225 - 2,235 (including Mag The Mighty, Ygritte, Harma, Styr and Donal Noye)
- Siege of Moat Cailin
- Raid on Saltpans
- Total deaths: entire town of Saltpans, maybe ~100
- fight by Deepwood Motte
- Taking of The Shields
- Siege of Dragonstone
Nobles
There were 186 confirmed nobles killed during The War of The Five Kings.
Famine
The main factor in this horrible war is most definitely famine. People are dying day-by-day, and food stores as well as farms are being depleted or put to the torch.
Even in the capital, King's Landing, it's becoming ever more difficult to get food; good quality food that isn't filled with people's shoes or people's flesh.
In a harsh Famine Winter, there can be as much as three times the number of deaths from famine as previous wars[1], therefore:
Future
Winter is coming. Most towns and cities don't have enough food stores and this winter is going to be a harsh one, both with the threat of the White Walkers and the impending Dance of Dragons; it's going to get even bloodier!
1. Yes, he gets revived later on by Thoros of Myr; count this as his first death.