The well-sourced article on Wookieepedia on Mace Windu gives the following explanation under Character Concept
The name "Mace Windu" (or Mace Windy) actually dates back to the earliest incarnation of Star Wars, a 13-page treatment written by George Lucas in 1973 called Journal of the Whills, Part I. The character Windy Marstrap is also derived from early incarnations of Mace Windu, becoming variously a brother of Leia in the rough draft and a friend of Luke's in the third draft.[67] A similar name—Mace Towani—appeared in the made-for-television Ewok films Caravan of Courage: An Ewok Adventure (1984) and Ewoks: The Battle for Endor (1985). An alien in Spare Parts (c. 1994) and Galaxy Guide 7: Mos Eisley (1993) also went by the name of Mace Windu, an abbreviation of his full name Macemillian-winduarté. The name Mace Windu was finally introduced into the films with The Phantom Menace (1999). Although a HoloNet article mentioning Mace Windu's participation in the Battle of Skor II explains Macemillian-winduarté's name, the coexistence of the names "Mace Towani" and "Mace Windu" may imply that "Mace" was a common name throughout the galaxy, or that Towani was simply named after Windu due to Windu's fame (given the fact that the Ewok films take place during the Galactic Civil War).