Two observations: first you are getting the strange output order in your sample code because the first BEGIN in script.pl has a spurious colon after it, turning it into a label and delaying its execution. Second, in the offending module in your real code, try putting print statements (not BEGIN{print} statements) within the import() function of that module; that's the next thing executed after the body of of the used Module, before use returns. So in your Module.pm example, it would become

package Module;

BEGIN { print 'beginning my module '.join(', ',@ARGV)."\n" }

# do lots of stuff

BEGIN { print 'ending my module '.join(', ',@ARGV)."\n" }

sub import {
    print 'starting module import '.join(', ',@ARGV)."\n";
    # stuff
    pop @ARGV;
    print 'ending module import '.join(', ',@ARGV)."\n";
}

1;
[download]

which produces the output

$ ./script.pl a b c
before using my module a, b, c
beginning my module a, b, c
ending my module a, b, c
starting module import a, b, c
ending module import a, b
after using my module a, b
[download]

Dave