It's been a while since I did battle with non-ASCII filenames on Windows, but from what I remember, Windows has some "quirks" in how it returns non-ASCII filenames to Perl, which is probably the root of the problem. While I haven't used these modules directly, I have seen them recommended in various other threads on similar topics (1113737, 1162804, 1170561, 1195063), and so I just wanted to highlight the AM's suggestion of Win32::Unicode. Also two of those threads mention Win32::LongPath as an alternative.

Update: More references: 1220286, 1210032, 1078587