Read the perldoc perlunicode. There you'll find
Interaction with Locales
Use of locales with Unicode data may lead to odd results. Currently, Perl attempts to
attach 8-bit locale info to characters in the range 0..255, but this technique is
demonstrably incorrect for locales that use characters above that range when mapped into
Unicode. Perl's Unicode support will also tend to run slower. Use of locales with
Unicode is discouraged.
In other words, since you are using UTF-8 encoding for your locale, you don't need to "use locale" in your program. The perl shall use appropriate UNICODE definitions to handle your strings. When you request locale support, you confuse perl and get unexpected things.
Basically, with UNICODE support of perl, you don't need to worry about locale. The locale settings become important only when the data leaves perl script. When this happens, the environment (for example shell) gets just sequence of bytes, which have to be somehow interpreted. The locale define, how they will be interpreted. So your perl code has to make sure that the data it outputs is suitable for the interpretation. So, effectively, you just need to make sure that your file-handles output data in correct encoding.