Amalekites and magic:
The Amalekites' ability to change into animals is brought by Rashi on Shmuel 1:15:3 and the Rid on the same verse, and mentioned as a midrash in the Kitzur Ba'al Haturim's commentary on Shemot 22:17. Their ability to use magic to flee from danger is brought in the longer commentary of Ba'al Haturim on Shemot 17:13 as something that "some [commentators] say".1 Their being sorcerers is mentioned also in Rabbi Chaim Paltiel's commentary on Shemot 17:13, where he writes that according to a midrash Amalek were sorcerers and therefore knew who would live throughout the entire year, and so those people were sent to do battle, knowing they wouldn't die. And so also write Rashi on verse 9, Chizkuni on verse 9 and Rabbeinu Efraim in his commentary on the same verse, per the Yerushalmi Rosh Hashanah 17b and Tanchuma Beshalach 28. This is also mentioned in Yalkut Shimoni on the Nach 564.
Explanation A: Agag and magic and his wife:
Many sources on Agag specifically having this ability were brought in this list of notes on a certain edition of a Machzor, on the term "בכשפיו מתגנב" in the "Yotzer for Shvi'i of Pesach" by Rabbi Yosef B'Rabbi Nissan, possibly a student of Rabbi El'azar Hakalir. The term itself comes from a stanza in the piyut that clearly refers to Shaul's battle with Amalek. Other sources are (plus a couple that I've found elsewhere, such as here):
A possible echoing of Rabbi Yosef's piyut in Rabbi Shimon b'Rabbi Yitzchak's Krovah for Rosh Hashanah "שבתי וראה":
"ידיד ה' אשר מלך תחלה...צוה על מחית המזנב...בחמלו מעדנת בכשפיו מתגנב..."
Translation: "The beloved of Hashem who was the first to rule...was commanded on annihilating he who attacked the stragglers...by his being merciful towards he who faltered but snuck around with his sorcery..."
In Rabbi Netanel ben Yeshayah's commentary on the Torah "Me'or Ha'afelah", pg. 247 in the Hebrew translation by Rabbi Yosef Qafich, it says:
"ולמה הסמיך זה אל מכשפה ללמד שהמכשפים פעמים עושים כשפים בעצמם ונהפכים לבהמות כמו אגג מלך עמלק שעשה עצמו שור ואשתו פרה ובאותה הלילה עיברה וברחה..."
Translation: "And why did he connect this to a witch, to teach that the sorcerers sometimes cast spells on themselves and change into animals, like Agag, King of Amalek, who turned himself into a bull and his wife a cow, and in that night she became pregnant and escaped..."
Rabbi Menachem Kasher in Torah Shlemah on Esther brings Rabbi Netanel ben Yeshayah's commentary on Esther, where he similarly writes:
"בן המדתא האגגי, מדתא היא אשתו של אגג, ובעת שהלך שאול להרוג את עמלק עשה אגג כישוף ונהפך שור שמן והפך את אשתו פרה וחמדו אותן לקרבן, ובאותה לילה עיבר אגג את מדתא ופרחה."
Translation: "Ben Hamedata Ha'agagi, Medata is the the wife of Agag, and when Shaul went to kill Amalek, Agag cast a spell and turned into a fat bull and changed his wife into a cow, and they coveted them as sacrifices, and in that night Agag cohabited with his wife Medata and she fled."
This is brought in Me'am Lo'ez on Shmuel 1:15:33 in the name of "Chachmei Ashkenaz":
"ויש במדרש קדום (חכמי אשכנז) שאגג הפך עצמו לשור ואשתו לפרה במעשה כשפים, והלך ועיבר את אשתו קודם שייהרג וממנו נולד המן ולפיכך נקרא על שמו."
Translation: "And in an ancient midrash (from Chachmei Ashkenaz) that Agag turned himself into a bull and his wife into a cow through sorcery, and he went and cohabited with his wife before he was killed and from him was born Haman, and for this he [Haman] was named after him."
The Razah in Midrash Hachefetz on Shemot 22:17 writes:
"...וי"א שהסמיך שוכב עם בהמה למכשף כי הם מכשפים לפעמים עצמם ויהיו לבהמה, כמו אגג שעשה עצמו שור ואשתו פרה נתעברה באותו הלילה והלידה מדתא...והוא הוליד את המן."
Translation: "...and there are some that say that he connected lying with an animal to a sorcerer because they sometimes cast spells on themselves and become animals, like Agag who turned himself into a bull and his wife into a cow and she became pregnant that night and gave birth to Medata...and he begot Haman."
Pa'anach Raza on Shemot 22:17 writes:
"מכשפה לא תחי' וסמיך לי' כל שוכב עם בהמה, שהמכשפות עושין עצמן לבהמות כבמעשה אגג ושניהם בסקילה."
Translation: "You shall not let a witch live, and near that all who lies with an animal, that the witches turn themselves into animals like in the story of Agag, and both are punishable by stoning."
Rabbeinu Bechayei states this is a midrash in his commentary on Devarim 25:19:
"...The Midrash also claims that the Amalekites made for themselves animals by means of sorcery, changing their genes to different species. This is why Samuel did not content himself with a general description fitting all animals. He used divinely inspired wisdom in order to outsmart them."
The Chida in Tzav'arei Shalal on the haftarah of Zachor writes in the name of Rabbi David Melamed:
"...והוא שידע שעבר אשתו ועשה כשפים להצילה ומשם יצא המן..."
Translation: "...and he who knew that he had cohabited with his wife and did sorcery to save her and from that came out Haman..."
This is also brought in the name of Rabbi David Melamed by the Chomat Anach on Shmuel 1:15:32.
Rabbi Shalom Shabazi in Midrash Chemdat Yamim wrote that Agag was able to shapeshift into an animal, but doesn't mention that that's how Haman's ancestors came to be born.
The bottom line is that it seems there used to be such a midrash, now apparently lost.
Explanation B: Agag and a slave:
Another explanation is that Agag cohabited with a slave woman on that one night he was still alive before Shmuel came and killed him. This is brought by the Alshech on Esther 2:5, Alshech on Tehillim 22:23, the Alshech on Shmuel 1:15, Etz Yosef on Esther Rabbah 5:4, Ben Yehoyada on Yoma 22b, Shem Mishmuel on Tetzaveh, Rabbi Chaim Vital in Pri Etz Hachaim and in Sha'ar Hapsukim, Rabbi Yoshiyahu Pinto on Terumah and Kli Yakar on Shmuel 1:15:32. And in Rabbi Tzemach Duran's commentary on Rabbi Yitzchak Giyat's song "Puria Yoma Denan", brought in his son's book Tiferet Yisrael, he also brings this idea:
"...וכמו שדרשו ג"כ ז"ל, שכאשר הביאו ונתנו בבית הסוהר בא על שפחה אחת ונתעברה ממנו, ומאותו עבור היה המן בעולם..."
Translation: "...and as they said as well, that when he [Shaul] brought him [Agag] to the jail, he cohabited with a slave and she became pregnant, and from that pregnancy came Haman to the world..."
According to this essay on the subject, the oldest source seems to be from Rabbi El'azar Hakalir's piyut "יזכר איבה לשכני", where he wrote about Agag:
"וזינה בשפחתו והולידה צפע המחלק"
Translation: "And he committed adultery with his slave girl and she gave birth to the dividing serpent"
Explanation C: Agag and an unknown virgin:
A third explanation is brought by the Rambam in his commentary on Esther 3:1, where he writes:
"...והיתה הסבה שהחיה שאול את אגג ולן באותו לילה כבול ולנה אתו בתולה, וכששוחחו בשיחתן וראה מן המלך שאול שרחם עליהם (בא אליה) והרתה באותו הלילה וברחה ביום השני..."
Translation: "...and that was the reason that Shaul let Agag live, and he slept that night tied up and with him slept a virgin, and when they spoke between them, and he saw that King Shaul was merciful toward them, he cohabited with her and she became pregnant that night and escaped on the second day..."
Misc.: Agag and an unknown woman:
Rabbi Shlomo Alkabetz on Esther 5:4 wrote that that one night that Agag was left alive allowed him to continue his lineage, but doesn't go into any details.
1 It's noted here and here that this was the reason that Shaul was to kill men, women, children and animals, because the Amalekites could disguise themselves as all of these.
