Were there any natural disasters that decisively changed the result of a later election by killing the electorate of one side?

Partial answer (which I thought of some time after asking the question): the case of the Trojan Horse.

According to the story, near the end of the Trojan War, the Greeks lifted the siege leaving a wooden horse behind. The wooden horse was actually a ruse, since it contained Greek soldiers within. The Trojans were debating what to do with the horse, with some wanting to burn it. Then a "natural disaster" killed the people who most wanted to burn the horse, leaving the other faction victorious and thereby ensuring the doom of the Trojans:

The most detailed description of Laocoön's grisly fate was provided by Quintus Smyrnaeus in Posthomerica, a later, literary version of events following the Iliad. According to Quintus, Laocoön begged the Trojans to set fire to the horse to ensure it was not a trick. Athena, angry with him and the Trojans, shook the ground around Laocoön's feet and painfully blinded him. The Trojans, watching this unfold, assumed Laocoön was punished for the Trojans' mutilating and doubting Sinon, the undercover Greek soldier sent to convince the Trojans to let him and the horse inside their city walls. Thus, the Trojans wheeled the great wooden Horse in. Laocoön did not give up trying to convince the Trojans to burn the horse, and Athena made him pay even further. She sent two giant sea serpents to strangle and kill him and his two sons. In another version of the story, it was said that Poseidon sent the sea serpents to strangle and kill Laocoön and his two sons.

This is still only a partial answer because:

• It's probably a myth.
• Getting killed by sea serpents is not exactly what most people would call a "natural disaster".

It seems that one basic assumption in the question is stable voting behaviour of affected people. That is likely a quite difficult to test hypothesis. Like in the old paradoxon that if the dumbest person moves from country A to B he might indeed raise the average intelligence of both countries?

If people are killed by a catastrophe those all cannot vote anymore. If it is an event that affects rich and poor differently an effect seems to be expected. However some analysis after Katrina concludes:

Voters whom the media portrayed as having likely higher costs of casting ballots are not necessarily so affected. Although flooding does decrease the probability that an individual casts a ballot, the relationship between flooding and race, partisan registration, and age are not key determi- nants of the likelihood that an individual casts a ballot. Furthermore, the depth of flooding does not have a constant effect on the probability that an individual casts a vote. That is, within areas of New Orleans that experienced significant flooding, worse flooding has a clear positive association with turnout. Also, heavier flooding is not associated, as might have been expected, with larger negative effects on citizens with fewer personal resources. Both of these findings are counterintuitive. […]

Individuals who live in areas that had large- scale flooding were actually more likely to vote in 2006 than others who suffered less flooding.
_{— Betsy Sinclair, Thad E. Hall, R. Michael Alvarez: "Flooding the Vote: Hurricane Katrina and Voter Participation in New Orleans", American Politics Research, Vol 39, Issue 5, 2011.}

But this is also an effect of very much concerted efforts in that area to compensate the natural effects of the storm.

Again in May, New Orleans’ voters had a weeklong opportunity to vote early, either in person at a satellite voting location or via an absentee ballot, and on May 20th in-town voters made their way to their local polling locations to choose the next mayor. By the end ofthe evening, Ray Nagin had been re-elected to another four-year term as mayor. He won 59,460 votes to Mitch Landrieu’s 54,131, a 5,329 vote difference that amounted to a 4 percent victory. Nagin won despite Landrieu’s spending advantage because of his ability to win white voters. While he only won 10 percent of white voters in the primary, Nagin captured around 20 percent of their votes in the runoff Landrieu again managed to secure to votes of around 20 percent of African-American voters, but since African-American voters comprised a majority of the electorate, Nagin’s 80-20 advantage with that group propelled him to victory (Krupa, 2006a).
_{— Brian Brox: "Elections and Voting in Post-Katrina New Orleans", Southern Studies: An InterdisciplinaryJournal of the South, Fall/Winter 2009, 16(2): 1-23.}

The assumed voting preference stability is contestable, though. Many voters in any system may flip their choices at any time (unlike: 'Republican/Democrat voters for life', 'Brexiteer forever'?).

One example were the voting behaviour did flip because of a natural disaster:

It is not so much related to really killing off a large part of the electorate, but the federal election 2002 in Germany is widely analysed as being hugely influenced by the floods of that year.

The then chancellor 'social-democrat' Schröder had run his course and accomplished not much, but forcing anti-social laws and precarious labour, on top of ousting Helmut Kohl from power. People liked the removal of Kohl but were pretty soon fed up with his neo-liberal and neo-conservative agenda of feeding the rich.

During the election campaign two outside events worked in his favour:

1. The planned Iraq war: the foreign policy stance was "nope, not coming" and people liked that (usually German electorate is strongly against any foreign military interventions and war mongering, but the right wing parties Greens, SPD, FDP and CDU/CSU just do it anyway, once elected and in power.)

2. The floods immediately provided ample picture opportunity of a "man in charge" wandering about the landscape in wellingtons and looking at things with rolled up sleeves. His main rival just reacted too late for that to be effective.

Only through two "chance events", the Oder flood in East Germany and the Iraq war, which Schröder deliberately used in his election campaign, was the SPD able to defend the government in the 2002 federal elections (Raschke 2003; Quandt 2005).
_{— Tim Spier & Ulrich von Alemann: "Die Sozialdemokratische Partei Deutschlands (SPD)", in: Oskar Niedermayer (Ed): "Handbuch Parteienforschung", Springer Fachmedien Wiesbaden, 2013, p444.}

_{— Michael Stürmer: "Als Schröder Stoiber im Hochwasser versenkte", Welt, 14.08.2012.}

_{— Günter Bannas: "Geschichte wiederholt sich nicht", FAZ, 26.08.2005.}

How reliable or valid this kind of analysis is might be a matter of dispute though. In the above example the main rival had a lot of disadvantages running against him: terrible public speaker, Bavarian, etc…

An in-depth study using a detailed, but limited methodology did not find a large influence

Kosta Bovan & Benjamin Banai & Irena Pavela Banai: "Do Natural Disasters Affect Voting Behavior? Evidence from Croatian Floods", PLOS Current Disasters, 2018.

But such disasters are always a great opportunity for politicians to make them appear as 'caring', when it benefits them:

After extensive testing for the sensitivity of my results, the most important findings reported in this paper provide clear evidence that governments increase their public spending after a large-scale natural disaster more when elections are upcoming in the same year.
_{— Jereon Klomp: "Election or Disaster Support?", The Journal of Development Studies Volume 56, Issue 1, 2020.}

It stands to reason that these freak and outside events influence voting behaviour beyond any remains of rationality, sorely lacking anyway:

Though we are barely two decades into the twenty-first century, we have already seen the dramatic ways in which terrorist attacks, natural disasters, extreme weather, and other calamities can affect impending and ongoing elections. We can help preserve the fundamental right to vote by carefully considering the issues such election emergencies raise ahead of time and crafting emergency statutes to empower election officials to respond appropriately.
_{— Michael T. Morley: "Election Emergencies: Voting in the Wake of Natural Disasters and Terrorist Attacks", Emory Law Journal, Vo 67, No 3, 2017.}

Natural disasters that actually killed a lot of people were the 2011 floods in Pakistan. The afected area was comparatively small, but the voter turnout was altered substantially depending on area and ex-ante flood risk. Meaning that areas with low prior experience of floods and government aid massively increased their voting while areas with highest prior floods actually decreased it.
_{— C. Christine Fair et al.: "Natural Disasters and Political Engagement: Evidence from the 2010-11 Pakistani Floods", 2015. (PDF)}

Pooling the available data suggests:

Disasters affect leader tenure. The positive significant coefficient estimates on the disasters variable in Models 9 and 11 indicate that the occurrence of a disaster will jeopardize a small coalition leader’s hold on office. Models 10 and 12 examine the effect of disasters in both the current and previous years. Joint hypothesis tests of the effects across these two years show that disasters increase the risk to autocrats. In contrast, disasters – at least low casualty ones – lower the risk of deposition in large coalition systems. Across the four models, the sum of the estimates of the disasters variables and their interaction with W is negative and generally statistically significant. Disasters help democratic leaders stay in power, but imperil autocrats. This result for democracies is consistent with prior evidence. Abney and Hill, Chen, Healy and Malhotra, and Reeves have shown that US leaders can benefit from the opportunity to disperse benefits and demonstrate competence in the aftermath of disasters; Olson and Gawronski also found evidence in favour of this hypothesis in their analysis of several case studies around the world. The story is reversed when it comes to evaluating disaster-related fatalities. The small statistically insignificant coefficient estimate on the deaths variable indicates that small coalition leaders are relatively immune to disaster-related deaths. However the estimates of the interactions between W and the deaths variables are larger, and joint hypothesis tests show that increased deaths impose a statistically significant threat to the tenure of large coalition leaders.
_{— Alejandro Quiroz Flores & Alastair Smith: "Leader Survival and Natural Disasters", British Journal of Political Science, Volume 43, Issue 4 October 2013 , pp. 821-843.}