For a strategy game where you are an emperor of an old, big, bureacuratic space empire in decline.
I have a trouble how to name law enforcers (the institution). Space Police does not fit empire theme at all, it gives the feel of a democratic society instead of an absolute dictatorship of an emperor...
How to call something that function like a space police in such game?
Lensmen. 
What's the scope of the empire? Solar, interstellar, galactic?
Some words you can work with are: Patrol, Security, Guard, Shield, Defense
Galactic Shield?
Department of Security?
Department of Interstellar Commerce and Trade (and the policing and taxing of it)?
Peace Enforcers, Peace Patrols, just plain 'Peacekeepers'
Civil Stability Department?
Department of Galactic Stability? ('Dogs' for sort)
Department of Galactic Defense?
If this is an oppressive dictatorship, I might name it something so innocuous sounding that it can't help but be interpreted as unsettling and ominous. Like the Ministry of Love in 1984.
Of course, since you said this is a declining empire, you might call it something that evokes an heroic, ancient tradition, albeit one that has since decayed into a corrupt group of thugs, unworthy of such a name. Maybe call them Paladins (to rip off history). Then any player who has seen a paladin in another work will instantly understand, upon watching them slag an entirely peaceful world because they were rumored to be plotting rebellion, that the empire has seen great times, but that all redeeming qualities have long since perished.
For stuff like this, I like to compile a short list of individual words and phrases and combine them in my head to see if anything particularly interesting falls out:
Titles:
Functional:
Other:
For example: State Security Office, Public Safety Commissariat, Imperial Secret Police, Directorate of Freedom and Security, and so on.
You could always browse around Wikipedia, like look at all the crazy secret police successor agencies in the Soviet Union. Personally, I would go for at least a really bureaucratic sounding name since this is the decline of an empire and a bureacracy-run-amok spaghetti soup of an acronym would just seem so appropriate.
Or, even go backwards and find a neat acronym and make up something that fits it. ISD, SIS, SIOPS, etc.
Interstellar Enforcement?
Cosmic L.E.O.?
Interplanetary Establishment of Legal Adherence?
For stuff like this, I like to compile a short list of individual words and phrases and combine them in my head to see if anything particularly interesting falls out:
Heh, a nice trick :)
There's absolute dictatorship and absolute dictatorship.
Bureaucratic names, the prevalent style in the suggestions so far, imply a stable and mature government in which a succession of people fills an established Emperor role.
To imply a recent and serious change police can be named in a variant of bureaucratic style that references "revolution", like in Iran and China, or something similar ("progress", "renewal", etc.) or the specific political entities and politically charged words of a specific revolution, like "soviets", "workers" and "people" in communist countries.
An autocratic conqueror who really founds an empire from scratch might have a "police" that evolves from his/her/its faithful followers and is named in peculiar ways (possibly unofficially). Characters could be scared of the proudly visible "purple shirts", the brutality of the "Kalonian Knights", the secret resources of the "Order of the Stick", and so on.
If police is important, consider multiple police or quasi-police forces, with different mandates, different characteristics, and different moral and political alignments.
For example, a military police that developed from navy units dedicated to crushing smugglers and pirates in space and apprehending fugitives can be a threat to appropriate characters, but far less evil than a Dissenter Assassination Department and its secret agents.
