You didn't specify that you could only use sed, so if you have access to xml_grep (see Merge multiple XML files from commend line, second answer), I would recommend that because it does a lot of the heavy work for you and for a simple merge job like this can be done in one command:
xml_grep --cond Record --wrap "ns0:collection" --descr 'xmlns:ns0="http://www.nwl.co.uknamespace/BillPrintExtractServiceService/1.0"' --encoding "UTF-8" *.xml
Test files:
test.xml
<?xml version="1.0" encoding="UTF-8" ?><ns0:collection
xmlns:ns0="http://www.nwl.co.uknamespace/BillPrintExtractServiceService/1.0"><Record>0""><Record>
Test
</Record></ns0:collection>
test1.xml
<?xml version="1.0" encoding="UTF-8" ?><ns0:collection
xmlns:ns0="http://www.nwl.co.uknamespace/BillPrintExtractServiceService/1.0"><Record>
Test 1<a>a</a><b c="c">d</b>
</Record></ns0:collection>
Result
<?xml version="1.0" encoding="UTF-8" ?>
<ns0:collection xmlns:ns0="http://www.nwl.co.uknamespace/BillPrintExtractServiceService/1.0">
<Record>
Test 1<a>a</a><b c="c">d</b></Record><Record>
Test
</Record>
</ns0:collection>
I prefer to use XML-aware tools when dealing with XML files, because the chance of messing up the structure with sed and friends is quite high and you can easily end up with a malformed XML document!