XML::XPath is not the only XPath implementation you can look at: XML::Filter::Dispatcher which has a complete XPath parser (at least you can reuse the YAPP grammar). You could also look at the way libxml2 (the base for XML::LibXML) does it. Even though it is written in C you might be able to re-use the data structure and the algorithms.

Finally, XPath is quite a complex standard, that goes way beyond the simple directory-like syntax that you are showing, it includes predicates, function calls... so it might not be easy to get a fast implementation of all of this (i.e a structure that speeds-up some queries might not be quite appropriate for others). DB-XML actually maintains user-defined XPath queries as indexes, that might be a good strategy.