Aus den Erwägungen:
2.1 Der Beschwerdeführer bringt hiergegen vor, er habe sich zum Zeitpunkt der vorinstanzlichen Verfügung nicht illegal in der Schweiz aufgehalten und noch weniger illegal gearbeitet. Als bulgarischer Staatsbürger sei es ihm gestattet, sich während 90 Tagen visumsfrei in der Schweiz aufzuhalten. Diese Frist sei noch nicht abgelaufen gewesen. Im Weiteren sei er im Zeitpunkt der Verfügung noch nicht rechtskräftig wegen illegaler Erwerbstätigkeit verurteilt gewesen, weshalb darauf auch nicht abgestellt werden dürfe, um ihn wegen Gefahr für die öffentliche Ordnung (oder fehlender Arbeitsbewilligung) aus der Schweiz wegzuweisen. Die Vorinstanz habe mit ihrer Vorgehensweise sein rechtliches Gehör (Unschuldsvermutung) in grobem Mass verletzt. Die angefochtene Verfügung müsse folglich aufgehoben werden.
2.2 Angehörige der Europäischen Union (EU-27) benötigen zur Einreise in die Schweiz lediglich einen gültigen heimatlichen Pass oder eine gültige Identitätskarte. Der Aufenthalt im Schengenraum ohne Erwerbstätigkeit von bis zu drei Monaten (90 Tage) innerhalb von sechs Monaten ist daher weder visums- noch bewilligungspflichtig. Darüber hinaus kann die Einreise und der Aufenthalt nur verweigert werden, wenn die persönliche Anwesenheit des betroffenen EU-Bürgers zu einer schwerwiegenden konkreten Gefährdung der öffentlichen Ordnung und Sicherheit führt (vgl. Anh. I Art. 5 des Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit [FZA]; Ziff. 2.2.1 und 12.1 der Weisungen und Erläuterungen des Bundesamtes für Migration [BFM] zum Freizügigkeitsabkommen [in der Fassung vom 1. Mai 2011] und Ziff. 3.1.1 derjenigen zum Ausländerbereich [in der Fassung vom 30. September 2011]). Insofern ist zu beachten, dass die Anordnung einer Wegweisung oder eines Einreiseverbots wegen Schwarzarbeit grundsätzlich nur in ausserordentlichen schweren Fällen möglich ist, andernfalls die hohen Anforderungen von Anhang I Artikel 5 FZA nicht erfüllt sind (vgl. Ziff. 12.1.1—12.1.2 der Weisungen und Erläuterungen des BFM zum Freizügigkeitsabkommen [in der Fassung vom 1. Mai 2011]).
2.3 Angesichts dieser Ausführungen muss geschlossen werden, dass der Beschwerdeführer als EU-Bürger, selbst wenn er rechtkräftig wegen illegaler Erwerbstätigkeit verurteilt worden wäre, deswegen nicht aus der Schweiz hätte weggewiesen werden dürfen. Ebenso wenig ist es zulässig, ihn während des 90-tägigen visumsfreien Aufenthaltes in der Schweiz aufgrund illegalen Aufenthaltes wegzuweisen. Die Wegweisung eines Angehörigen eines EU-Staates gestützt auf Artikel 64 Absatz 1 AuG kommt vielmehr nur im engen Rahmen der Bestimmungen des FZA und dessen Ausführungstexten in Betracht. (Justiz- und Sicherheitsdepartement, 13. Dezember 2011)