I think we can get some idea from Alex the Parrot. Alex could answer "Yellow" when asked "What color key?" and answer "Key" when asked "What object yellow?" each when shown an array of different objects of different colors. He also appeared to be able to count up to six, answering "Five" when shown a table full of cubes of many colors and asked, "How many blue?"
But now we have to ask, did Alex go around at various times skwawking out "Key" and "Yellow" and "Five" at random times? To be honest, I do not know. But what I can infer from the article linked above and the few appearances Alex made in various TV documentaries I have seen, he might have at first, but later on, as he learned more what was expected, he did not. For example, the article states, "Pepperberg did not claim that Alex could use 'language', instead saying that he used a two-way communications code." This suggests that Alex would not have randomly uttered words, since this would not have gained him anything in the communication with his trainers.
Now on to how long it takes. Alex lived for 31 years and was in near constant training for his entire life, just beginning to learn the concept of under and over at the time of his passing. But we don't need our singing magic parrot to achieve that level necessarily, just to make fire on demand and never at any other time. I'm guessing here, but I think we can get there in under 10 years. Of course, during this time we need to keep trainee parrots in secure and isolated environments where risk to self and others is minimized.
Next (thanks JGreenwell for pointing this out), we have to consider whether a parrot can acurately reproduce the sounds. This was a problem with Alex as I recall, at first saying "Key" as a raspy guttural sound. But the trainer used modeling. The trainer asked a fellow human assistant, "What object yellow?" and the assistant answered mimicking Alex. The trainer then said, "Say it better," then the assistant answered again in his or her normal voice, then received a cracker. Alex caught on and rapidly said his words in very clear diction, or he didn't get his cracker. Your world's trainers will need to employ similar techniques.
Finally, users will obviously not be able to train the parrots themselves. After all, if getting the melody and rhythm just right is crucial to the spell, the tone-deaf person won't be the proper role model. This parallels Real World (TM) training of service dogs for the blind. A whole industry will spring up on your world where certain skilled magicians specialize in just this service, fostering and training young parrots, and when ready, placing them with those in need. This can give you an interesting plot point- in your society, is this service considered a commodity to be bought at a price (like Merry Maids), or a public benefit sponsored by volunteers and donations (like service dogs)?
In summary, yes it is possible. It will just take time, care, and skill.
(I just have to say it. This is among the most absurd questions and answers I have ever participated in. Bless this SE!)