The spell only works on non-magical clubs or quarterstaffs. Magical staves are not generally quarterstaffs, and those that do function as quarterstaffs are all enchanted. The Staff of Fire, to use your example, is a magical staff but not a quarterstaff.
Quarterstaffs are weapons. The are balanced for combat, made out of wood with the strength and flexibility to withstand large impacts, etc. Enchanting one requires the Craft Magic Arms and Armor feat. An example would be a +2 shocking quarterstaff. Shillelagh wouldn't work on this because it is enchanted.
Magical Staves are spell-trigger items. They are made out of exotic materials that enable them to store and channel magic. These materials are often fragile. Enchanting one requires the Craft Magic Staves feat. An example would be a Staff of Fire. Shillelagh wouldn't work on this because it is not a quarterstaff.
Despite the similar names and their general shapes, quarterstaffs and magical staves are very different things.
Except when they are both.
There are a few magical staves that also function as enchanted quarterstaffs. These require both the Craft Magic Staves feat and the Craft Magic Arms and Armor feat to create. An example is a Staff of Power. Shillelagh won't work on this because it functions as a +2 quarterstaff.
There are no magical staffs in the rulebooks that also function as non-magical quarterstaffs, so there are none that can have Shillelagh cast on them.
I really wish Shillelagh would work the way that you are trying to use it. I've loved the spell for decades, and my Staff Magus would love to be able to use it on his staves.