As far as I can see, the problem isn't the tilde so much as the unescaped character just before the tilde. It's the same as your separator. If you use a slightly different syntax for the search and replace, you can do the transformation without issue.
~/perl/monks$ cat test_tilde.pl
#!/usr/bin/perl
use warnings;
use strict;
my $test = "This is a test
of a replacement
string, really (example.com)
and truly.";
print $test, "\n";
$test =~ s|example\.com|12\.23\.56\.78\/\~example|g;
print $test, "\n";
The output is:
~/perl/monks$ ./test_tilde.pl
This is a test
of a replacement
string, really (example.com)
and truly.
This is a test
of a replacement
string, really (12.23.56.78/~example)
and truly.