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.