I see. You shouldn't need to worry about that, but you could solve it with something like this (in your program)

my $lib;
BEGIN {
    my $bin = '$PREFIX/bin';
    $bin =~ s~bin$~~;
    $lib = $Config::Config{sitelib};
    $lib =~ s~^\Q$Config::Config{siteprefix}\E~$bin~;
}
use lib $lib;
[download]

If a user is intelligent enough to make use of the PREFIX argument, he should be intelligent enough to make use of PERL5LIB, definetly something you shouldn't worry about.