If order matters, your subroutine in_list can simply check if the first element of list A ($lsa->[0]) was equal to the first element of list B ($lsb->[0]). If so, then the remainder of list A must be a subset of the remainder of list B. If not, then list A must be a subset of the remainder of list B. If list A is empty, it is (per definition) a subset of list B. If list B is empty, then list A cannot be a subset (unless it is empty itself).

The above description (if it's correct which I leave to you to check) would lead to the following algorithm, which destroys both lists:

sub in_list_recursive {
    my ($lsa,$lsb) = @_;
    if (@$lsa == 0) {
        return 1; # yay

    } elsif (@$lsb == 0) {
        return;   # nay

    } elsif ($lsa->[0] == $lsb->[0]) {
        shift @$lsa;
        shift @$lsb;
        return in_list_recursive( $lsa, $lsb );

    } else {
        shift @$lsb;    
        return in_list_recursive( $lsa, $lsb );
    };
};
[download]

This algorithm is far easier written using a loop variable and a nondestructive approach to the lists, but the conversion is left to you.