You'll need to supply a custom sorting sub that crafts an appropriate sort key:

my $t= parse XML::Twig::Elt(\*DATA);
$t->sort_children( sub {
    my $elt = shift;
    my $top = $elt->att('attribute');
    my $kid = $elt->first_child->tag;
    return $top . $kid;
});
$_->print for $t->children;
[download]

Produces:

<parent attribute="info1"><Child10><childinfo Number="1" attrib2="info
+3"/></Child10></parent>
<parent attribute="info1"><Child12><childinfo Number="1" attrib2="info
+3"/></Child12></parent>
<parent attribute="info1"><Child2><childinfo Number="1" attrib2="info3
+"/></Child2></parent>
<parent attribute="info1"><Child3><childinfo Number="1" attrib2="info3
+"/></Child3></parent>
<parent attribute="info1"><Child4><childinfo Number="1" attrib2="info3
+"/></Child4></parent>
<parent attribute="info1"><Child5><childinfo Number="1" attrib2="info3
+"/></Child5></parent>
<parent attribute="info1"><Child6><childinfo Number="1" attrib2="info3
+"/></Child6></parent>
<parent attribute="info1"><Child9><childinfo Number="1" attrib2="info3
+"/></Child9></parent>
<parent attribute="info2"><Child8><childinfo Number="2" attrib2="info3
+"/></Child8></parent>
<parent attribute="info3"><Child1><childinfo Number="3" attrib2="info3
+"/></Child1></parent>
<parent attribute="info4"><Child1><childinfo Number="4" attrib2="info3
+"/></Child1></parent>
<parent attribute="info5"><Child7><childinfo Number="5" attrib2="info3
+"/></Child7></parent>
[download]

But you'll notice that the unfortunate naming of the ChildNN tags makes Child 10 sort before Child2. You can hack at the naming to get the proper order, but it requires having a firm knowledge of your data invariants. Here would be a reasonable attempt though:

my $t= parse XML::Twig::Elt(\*DATA);
$t->sort_children( sub {
    my $elt = shift;
    my $top = $elt->att('attribute');
    my $kid = sprintf '%04d', ($elt->first_child->tag =~ s/Child//r);
    return $top . $kid;
});
$_->print for $t->children;
[download]

Produces:

<parent attribute="info1"><Child2><childinfo Number="1" attrib2="info3
+"/></Child2></parent>
<parent attribute="info1"><Child3><childinfo Number="1" attrib2="info3
+"/></Child3></parent>
<parent attribute="info1"><Child4><childinfo Number="1" attrib2="info3
+"/></Child4></parent>
<parent attribute="info1"><Child5><childinfo Number="1" attrib2="info3
+"/></Child5></parent>
<parent attribute="info1"><Child6><childinfo Number="1" attrib2="info3
+"/></Child6></parent>
<parent attribute="info1"><Child9><childinfo Number="1" attrib2="info3
+"/></Child9></parent>
<parent attribute="info1"><Child10><childinfo Number="1" attrib2="info
+3"/></Child10></parent>
<parent attribute="info1"><Child12><childinfo Number="1" attrib2="info
+3"/></Child12></parent>
<parent attribute="info2"><Child8><childinfo Number="2" attrib2="info3
+"/></Child8></parent>
<parent attribute="info3"><Child1><childinfo Number="3" attrib2="info3
+"/></Child1></parent>
<parent attribute="info4"><Child1><childinfo Number="4" attrib2="info3
+"/></Child1></parent>
<parent attribute="info5"><Child7><childinfo Number="5" attrib2="info3
+"/></Child7></parent>
[download]