The Wizard of Cosme Velho is a posthumous nickname, popularized from 1958 on. Cosme Velho is the street in Rio de Janeiro where Machado lived, at number 18, from 1883 until his death in 1908, according to Wikipedia. As for the word wizard, it evokes the idea of literary magic, but the sources consulted do not document the choice of word; the magazine Pesquisa FAPESP takes up the image in the title of a feature on Machado's "historical magic," which, according to Sidney Chalhoub, knew how to translate the complexity of his time.
Many people attribute the invention of the nickname to Carlos Drummond de Andrade, but he himself acknowledged, in a chronicle of September 11, 1964 in the Morning Mail, that paternity was not his. The critic Moysés Vellinho recorded the term in the book Letras da província (Porto Alegre, 1944), according to Augusto Meyer, who was already using it before Drummond.
What made the nickname famous was the poem "A um bruxo, com amor" ("To a Wizard, with Love"), by Drummond, published on September 28, 1958 in the Morning Mail and later in the book Poemas (1959). The journalist Valdemar Cavalcanti spread the expression in the press at the end of that year.
A popular story also circulates, recorded in Wikipedia, that neighbors gave him the nickname on seeing Machado burn letters in a cauldron. For some biographers, it is a legend.