Deleting items one at a time is quite inefficient. You're best bet, if it's a feasible option, is to just delete the entire list and re-create it. You can save it as a template first so that all of the column metadata will be maintained. The downside here is that you get a new GUID for the list, so references to the list by GUID (i.e. workflows, alerts, and certain other types of out of the box functionality) will break. This is very fast though, and it's a constant time regardless of the size of the list.
If that's not an option (which it always won't be) then the next best choice is to use batches. The SPWeb.ProcessBatchData method will allow you to send batches of deletions together (I usually like to send batches of 500-1000) which will be quite a bit faster than individual deletion. There are a lot of code examples of using this, but most of what I've found is all in C# code. If switching to a C# console app is an option you could use these examples directly, if not then it's certainly a possibility to convert them to powershell code as you still have access to the same library. Here is a link to the first example of using batch processing that I came across; but there are certainly others in google. I've coped the code on that page below for reference:
// 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();
}
}