Once you leave the baggage claim area look for "Depature" signs, you have to go up one level ( train station would be down one level ). Once you're in the main departure hall look for the empore at the end of the hall, above security checkpoints 2/3/4. The border police station is up there.
Hint: look for the Starbucks signs, the police station is to the left of the starbucks.