Nice work on a mind-bending puzzle. I refactored it some to combine base cases and whatnot and came up with this probably-too-dense version:

sub my_make_change {
  my $amount = shift;
  my $coin = shift || -1;
  return(
    map {
       my $n = $_;
       map [ [ $n, $coin ], @$_ ],
           ($n*$coin == $amount
            ? []
            : my_make_change( $amount - $n*$coin, @_ ));
    } (0..$amount/$coin)
  );
}
[download]

The output includes zeroes for any denominations on the left, which coincidentally makes the output tidier (or undesirably verbose, depending on your viewpoint).