This is addressed directly in the link to Rashi you provide:
[Midrash Aggadah , Yalkut Shimoni from Midrash Yelammedenu . Note that in these sources, the Amalekites changed their dress as well, and that version is found also in the Reggio edition of Rashi . The Yemenite manuscript, however, conforms with our reading. See Chavel fn. 87, Yosef Hallel , Leket Bahir fn. ד. See also Num. Rabbah 19:20.]
However, assuming that this is the correct reading, then obtaining and outfitting an entire army with Canaanite clothing is quite expansive, and might not be doable on short time. Meanwhile, being citizens of greater Mesopotamia, they might already know enough Canaanite to get by, and can make certain they are overheard.
But all this is a kasha on a medrash. I suspect that if the clothing/language divide is authentic, then that detail is derived from a close reading of the pesukim. And I don't know that it is useful or productive to ask questions of this sort. Even if this midrash was intended literally and is historical, we cannot necessarily know the answer. It is a kasha on a maaseh. And any answers we produce might be random and untrue.
The goal / background of the midrash, by the way, is to address the issue that it seems that this section was added by Yehoshua, describing the actual conquest inside Eretz Yisrael. (See Ibn Ezra for a rejection, or just see this post for details,. and perhaps here as well.) The Canaanite king of Arad, and the conquest of Chormah, is described in sefer Yehoshua. By making these Canaanites (with some Scriptural justification), we explain why these are describes as Canaanites. This avenue of exploration is, IMHO, much more productive.
In terms of Canaanites being specifically black, I'm not so positive about that. Despite midrashim one might drum up, I think I can drum up counter-midrashim. Specifically, the midrash in which Rabbi Yuda ben Simon attributes a statement of Avraham to his wife as they are about to enter Egypt, coming from the land of Canaan.