A sample of creating a folder and subfolders within SharePoint 2007 lists can be found below:
/// <summary>
/// As checked in U2U CAML query builder, this is valid in
/// <Batch PreCalc='TRUE' OnError='Continue' RootFolder='/Purchase Order Forms V2'>
///<Method ID='1' Cmd='New'><Field Name='ID'>New</Field><Field Name='FSObjType'>1</Field><Field Name='BaseName'>DDkTest2</Field></Method></Batch>
/// THIS Works for Subfolders
/// <Batch PreCalc='TRUE' OnError='Continue' RootFolder='/Purchase Order Forms V2/2010_01_January'>
/// <Method ID='1' Cmd='New'><Field Name='ID'>New</Field><Field Name='FSObjType'>1</Field><Field Name='BaseName'>DDkTest2</Field></Method></Batch>
/// </summary>
private void CreateFolder(string listName, string rootSubFolderName, string newFolderName)
{
ListsSoapClient client = new ListsSoapClient(); //TODO: Change to use WCF Client Factory
//Correct invalid characters
newFolderName = newFolderName.Replace(":", "_");
string rootFolder = rootSubFolderName.Length > 0 ? string.Format("/{0}/{1}", listName, rootSubFolderName) : listName;
string xmlCommand = string.Format("<Method ID='1' Cmd='New'><Field Name='ID'>New</Field><Field Name='FSObjType'>1</Field><Field Name='BaseName'>{1}</Field></Method>", rootFolder, newFolderName);
client.ClientCredentials.UserName.UserName = ConfigHelper.SharePointServiceUserName;
client.ClientCredentials.UserName.Password = ConfigHelper.SharePointServicePassword;
XmlDocument doc = new XmlDocument();
System.Xml.XmlElement batchNode = doc.CreateElement("Batch");
batchNode.SetAttribute("OnError", "Continue");
//Insert / to front as it is required by web service.
if (!rootFolder.StartsWith("/"))
rootFolder = string.Format("/{0}",rootFolder);
batchNode.SetAttribute("RootFolder", rootFolder);
batchNode.InnerXml = xmlCommand;
XmlNode resultNode = client.UpdateListItems(listName, batchNode;
}