use Encode;
...

my $string = "...";  # wherever you get your euc string from;
$string = decode( "euc-jp", $string );  # now it's a utf8 string;

... # plug it into the url as described earlier