Build embedded XML based on string containment
Because you have the overall root node, (a bit confusing that it changes name from root to paths between the two versions) there shouldn't actually be any inherent difference between nodes of the form "1/" and nodes of the form "1/2/" or longer. It should be possible to completely remove the first loop, and just have a special case definition of parent_path to point it to the actual root. 

If you do that, questions about whether dicts or sets are faster for deleting the length one paths, or suitably order preserving, or anything else, become a moot point. There's nothing left that you can't just do directly on lists/arrays, and for single pass iteration they are almost certainly the fastest option.

Memory consumption is something that I can't helpfully speculate about. It will depend on the particulars of your xml library and data. It's a problem if you're running out of memory, in which case profile it to check the usage is where you expect. 
If you're allowed to mutate the input array, and are worried about memory, you'd get some small savings and possibly a small efficiency boost for doing the sort in place rather than using sorted. However, you'd need a streaming XML writer (and some moderately knotty logic about when things can be committed) to make a significant difference. As far as I can see from the docs, xml.etree.ElementTree does not have inbuilt support for such streaming.

In terms of runtime, I wouldn't want to speculate about efficiency without measuring it. It might be that you could speed up the regex search, for example, by using re.compile ahead of time. That's unlikely to harm, but it can't help much if parsing the regex is taking an insignificant amount of time to begin with.

Code style, it would be nice to use more descriptive names, and in particular to avoid single letter variables. The comments, especially the comment on the sorting explaining the subtle bug in the naive version, are very helpful.