The most efficient way to a lot of transaction in SharePoint is using of SPWeb.ProcessBatchData method. For deleting operations there are very helpfull post. Code exaple from that post:
// We prepare a String.Format with a String.Format, this is why we have a {{0}}
string command = String.Format("<Method><SetList Scope=\"Request\">{0}</SetList><SetVar Name=\"ID\">{{0}}</SetVar><SetVar Name=\"Cmd\">Delete</SetVar><SetVar Name=\"owsfileref\">{{1}}</SetVar></Method>", list.ID);
// We get everything but we limit the result to 100 rows
SPQuery q = new SPQuery();
q.RowLimit = 100;
// While there's something left
while (list.ItemCount > 0)
{
// We get the results
SPListItemCollection coll = list.GetItems(q);
StringBuilder sbDelete = new StringBuilder();
sbDelete.Append("<?xml version=\"1.0\" encoding=\"UTF-8\"?><Batch>");
Guid[] ids = new Guid[coll.Count];
for (int i=0;i<coll.Count;i++)
{
SPListItem item = coll[i];
sbDelete.Append(string.Format(command, item.ID.ToString(), item.File.ServerRelativeUrl));
ids[i] = item.UniqueId;
}
sbDelete.Append("</Batch>");
// We execute it
web.ProcessBatchData(sbDelete.ToString());
//We remove items from recyclebin
web.RecycleBin.Delete(ids);
list.Update();
}
}