It was already recommended. Pass file handle instead of file name to HTML::TreeBuilder method. This should make sure that your input is interpreted as UTF-8. Then you have to make sure that your STDOUT is also reopened for using UTF-8 encoding.
And of course, check what is actual encoding of your input files.
You also should get good understanding on difference between "characters" and "octets". In few words, there is Unicode standard which assigns 4 octects (integer number) to each known "character" (image). Data files may use either these octects, or any other system. Files don't contain "characters", only octets. When perl reads files, it gets octets. Now, you want perl to work with "characters" corresponding to those octets. So you have to tell perl how to map octets to characters. For this, the "encoding" rule for file handles can be used. But you have to provide correct map. Now, after perl has worked with "characters" you want it to save results in file again. But for file you need "octets", not "characters". Again perl needs from you a map on how to convert characters to octets. That is why you should specify encoding for your STDOUT.
The fact, that you get some of the files correctly does not mean anything. All depends on encoding of the text that you have there. Things may work for some cases even when they are generally wrong.