My proposal was: Read your desired XML with XML::Simple, use Data::Dumper to see what the resulting structure is, then create it from all your data, and use XMLout to write your xml file. Here is the script to do that.

But then I thought: Will this work? All this effort. Let's test first and look at what XMLout does to what XMLin has created. And see: the output is different.

use strict;
use warnings;
use Data::Dumper;
use XML::Simple;
my $xml = <<XML;
  <Data>    
    <Root1>
        <TBLA>    
            <NEW1>
                <KEY>KEY6</KEY>
            </NEW1>              
            <NEW2>
                <KEY>KEY9</KEY>
                <KEY>KEY10</KEY>
            </NEW2>              
            <MODIFIED>
                <KEY name ="KEY1">
                    <COLA>
                        <oldvalue>A</oldvalue>
                        <newvalue>B</newvalue>    
                    </COLA> 
                    <COLB>    
                        <oldvalue>D</oldvalue>    
                        <newvalue>E</newvalue>     
                    </COLB>
                </KEY>
                <KEY name ="KEY3">
                    <COLX>
                        <oldvalue>M</oldvalue>
                        <newvalue>N</newvalue>    
                    </COLX> 
                </KEY>
            </MODIFIED>     
        </TBLA>
    </Root1>        
    </Data>
XML

my $ref = XMLin( $xml );
print Dumper($ref);
print XMLout( $ref, RootName=>"Data" );
[download]

which creates

<Data>
  <Root1 name="TBLA">
    <MODIFIED name="KEY">
      <KEY1 name="COLA" newvalue="B" oldvalue="A" />
      <KEY1 name="COLB" newvalue="E" oldvalue="D" />
      <KEY3 name="COLX" newvalue="N" oldvalue="M" />
    </MODIFIED>
    <NEW1 KEY="KEY6" />
    <NEW2>
      <KEY>KEY9</KEY>
      <KEY>KEY10</KEY>
    </NEW2>
  </Root1>
</Data>
[download]

The question now is: Is that ok for you? Or do you need more control, in which case there are a number of options in XML::Simple you can play with or you have to take another route.

PS: There were a number of inconsistencies in the sample xml you have provided.