検索文字列で 〜 にマッチするようにして、
置換文字列を make_link みたいな関数にして /e で評価する。
その関数の中で 〜 → ~ の変換を行う。とか。

sub make_link {
  my $url = shift;
  $url =~ s/〜/~/;
  return qq{<A HREF="$url" TARGET="_blank">$url</A>};
}

$tmp_data =~ s/(https?\:\/\/[^\s|\:|\<]+)\.(\/?)([\-_\.\!\~〜\*\'\(\)a-zA-Z0-9\;\/\?\:\@\&\=\+\$\,\%\#]*)/ make_link("$1.$2$3$4") /ieg;