To create a new folder using the DWS web service, first create a data connection that receives data from a web service. The URL looks like this:
http://<yourShPServer>/_vti_bin/DWS.asmx
Replace <yourShPServer> with your actual server URL.
When you click next, there will be some methods you can choose from. Select CreateFolder.
In your form, when you want to create the folder, set the url query field of the new data connection to the folder you want in a rule:
Shared Documents/DepartmentX/SomeotherThing
You can use a concat formula:
concat("Shared Documents/", my:DepartmentField, "/", my:SomeOtherField)
Then for the next rule, query using a data connection -- this will be the data connection you just created and set the URL for. This will create the folder if it does not already exist.
However, I think what you are then wanting to do is submit your form to that new folder. This thread has a code sample you can use, if you are comfortable with code. qRules has a command you can use (ChangeSubmitUrl) which may be a better way to go, depending on your coding skill level.
EDIT: I was mistaked about this web service -- while it will create a folder in a document library, it apparently will NOT in a form library. It looks like the UpdateListItems method of the Lists web service may work, but I've not tried that.