But why are we speaking of an "Andorian Empire" in the first place? No such thing has ever been mentioned in dialogue.
It is an extrapolation based on an isolated piece of information true, but this is common in examination of Star Trek. The Andorian military force were call the Imperial Guard on multiple occasions, so it is an indication that the Andorian people do live in an Interstellar Empire, and are the subjects of an Emperor/Empress.
Or as you pointed out, the Imperial Guard might simply be a hold over term, from an earlier age. The Andorian nation's formal title has never been used on screen, what information we do have leans more towards Empire, than away from it.