While it is true that Pharoah later regretted letting the Hebrews leave on the 15th of Nissan, this was indeed the day that the exile of Egypt ended, and that seems to be what the seder night commemorates, i.e. the Exodus. Indeed, the final destruction of the subjugation of the Hebrews to the Egyptians is also commemorated on the 21st of Nissan. As such, it seems it is the end of subjugation and the finality of redemption that is typically celebrated according to both biblical and rabbinic/traditional norms.
It would after all be odd to celebrate a day when fighting was ongoing and there was a continued threat of Judean suffering, subjugation, and/or annihilation. We thus find that the 25th of Kislev was chosen as the day to commemorate the victory over the Syrian-Greeks, when there a day of rest from the fighting (see, e.g., the Tur explaining why it is called Chanuka).
Likewise, the Megilla itself explains the appropriate days for commemorating the salvation from Haman's machinations:
וַיִּֽקָּהֲל֞וּ היהודיים [הַיְּהוּדִ֣ים] אֲשֶׁר־בְּשׁוּשָׁ֗ן גַּ֠ם בְּי֣וֹם אַרְבָּעָ֤ה עָשָׂר֙ לְחֹ֣דֶשׁ אֲדָ֔ר וַיַּֽהַרְג֣וּ בְשׁוּשָׁ֔ן שְׁלֹ֥שׁ מֵא֖וֹת אִ֑ישׁ וּבַ֨בִּזָּ֔ה לֹ֥א שָׁלְח֖וּ אֶת־יָדָֽם׃
and the Jews in Shushan mustered again on the fourteenth day of Adar
and slew three hundred men in Shushan. But they did not lay hands on
וּשְׁאָ֣ר הַיְּהוּדִ֡ים אֲשֶׁר֩ בִּמְדִינ֨וֹת הַמֶּ֜לֶךְ נִקְהֲל֣וּ ׀
וְעָמֹ֣ד עַל־נַפְשָׁ֗ם וְנ֙וֹחַ֙ מֵאֹ֣יְבֵיהֶ֔ם וְהָרֹג֙
בְּשֹׂ֣נְאֵיהֶ֔ם חֲמִשָּׁ֥ה וְשִׁבְעִ֖ים אָ֑לֶף וּבַ֨בִּזָּ֔ה לֹ֥א
The rest of the Jews, those in the king’s provinces, likewise mustered
and fought for their lives. They disposed of their enemies, killing
seventy-five thousand of their foes; but they did not lay hands on the
בְּיוֹם־שְׁלֹשָׁ֥ה עָשָׂ֖ר לְחֹ֣דֶשׁ אֲדָ֑ר וְנ֗וֹחַ בְּאַרְבָּעָ֤ה
עָשָׂר֙ בּ֔וֹ וְעָשֹׂ֣ה אֹת֔וֹ י֖וֹם מִשְׁתֶּ֥ה וְשִׂמְחָֽה׃
That was on the thirteenth day of the month of Adar; and they rested
on the fourteenth day and made it a day of feasting and merrymaking. (
והיהודיים [וְהַיְּהוּדִ֣ים] אֲשֶׁר־בְּשׁוּשָׁ֗ן נִקְהֲלוּ֙
בִּשְׁלֹשָׁ֤ה עָשָׂר֙ בּ֔וֹ וּבְאַרְבָּעָ֥ה עָשָׂ֖ר בּ֑וֹ וְנ֗וֹחַ
בַּחֲמִשָּׁ֤ה עָשָׂר֙ בּ֔וֹ וְעָשֹׂ֣ה אֹת֔וֹ י֖וֹם מִשְׁתֶּ֥ה
But the Jews in Shushan mustered on both the thirteenth and fourteenth
days, and so rested on the fifteenth, and made it a day of feasting
עַל־כֵּ֞ן הַיְּהוּדִ֣ים הפרוזים [הַפְּרָזִ֗ים] הַיֹּשְׁבִים֮ בְּעָרֵ֣י
הַפְּרָזוֹת֒ עֹשִׂ֗ים אֵ֠ת י֣וֹם אַרְבָּעָ֤ה עָשָׂר֙ לְחֹ֣דֶשׁ אֲדָ֔ר
שִׂמְחָ֥ה וּמִשְׁתֶּ֖ה וְי֣וֹם ט֑וֹב וּמִשְׁל֥וֹחַ מָנ֖וֹת אִ֥ישׁ
That is why village Jews, who live in unwalled towns, observe the fourteenth day of the month of Adar and make it a day of merrymaking and feasting, and as a holiday and an occasion for sending gifts to one another.
Ultimately, Haman was an individual. The Judean people were threatened by their myriad enemies and the unrepealed decree of Ahasuerus enabling their destruction. Till they emerged victorious, there likely remained uncertainty and anxiety regarding what would be the ultimate outcome. Perhaps that itself is commemorated by the fast of the 13th.
(For a somewhat related question, see here.)