Probably Encode.pm loads another module for handling UTF-16.

$ perl -le 'binmode STDIN, ":encoding(utf-16)"; print join " ", keys %
+INC'
bytes.pm warnings/register.pm XSLoader.pm Encode/Alias.pm Exporter.pm 
+vars.pm strict.pm PerlIO/encoding.pm Encode/Unicode.pm Encode/Config.
+pm Encode/Encoding.pm PerlIO.pm warnings.pm Encode.pm base.pm
[download]

Try to include those modules in your executable, maybe it works then?