You are correct in that the web service response captures the response XML into a Memo Data Element. Besides using the Parse Action, you can also use the Calculate action with the xPath function. This allows you some better control over locating data within the XML response.
The response parsing is pretty basic and limited to what I've described above. For anything more advanced than that, we might recommend a custom workflow action written in Java. It would have the ability to perform much more advanced operations.