I don't get that, even though your module doesn't return an object ( compared to Attribute::Constructor ), trace gets called if the phase is BEGIN

$ perl -le " eval qq/use Junk;/; print Junk->new "
Junk.pm(22) called with [Junk]
Junk.pm(22): returning [ Junk=HASH(0x3f8d1c) ]
1

$ cat Junk.pm
package Junk;
use Attribute::Handlers;

#~ sub TRACE :ATTR(CODE,CHECK) {
#~ sub TRACE :ATTR(CODE,INIT,CHECK) {
#~ sub TRACE :ATTR(CODE,INIT) {
sub TRACE :ATTR(CODE,BEGIN) {
#~ sub TRACE :ATTR(CODE) {
    my ($pkg, $sym, $ref, $attr, $data, $phase, $file, $line) = @_;
    *{ $sym } = sub {
        warn "$file($line) called with [@_]\n";
        my( @rc )= &$ref;
        warn "$file($line): returning [ @rc ]\n";
    }
}

sub new :TRACE {
    my $instance        = shift;
    my $class           = ref($instance) || $instance;
    my $self            = {};
    return bless($self, $class);
}
1;
[download]