You can probably find out where and why your program is failing by adding error detection and reporting.

Every time you perform a function that could fail, you should check to determine whether or not it failed and if it failed you should write an appropriate error message. For example, you could change your first two loops to be something like the following:

while (<*>) {
    $o = $_;
    s/\ /\¬/g;
    rename( $o, $_ ) or die "rename $o to $_: $!";
}
foreach (<*.avi>) {
    $cmd = "mkvmerge $_ -o ";
    s/\.avi$/.mkv/;
    $cmd .= $_;
    print "$cmd\n";
    system($cmd) == 0 or die "$cmd: failed with status $?";
}
[download]

Also, although it might make no difference here, I suggest you use strict and warnings, by adding the following near the top of your file:

use strict;
use warnings;
[download]

See Use strict and warnings for more information on strict and warnings.