I've never used it for updating, but XML::LibXML's XPath support is very handy for finding nodes quickly.

Another option would be to use XML::SAX to construct a pipeline reading at one end, modifying as needed in the middle and writing out the new file at the end. That would be an excellent choice if your files could be too large to load into memory all at once.

-sam