I turns out that the issue was not with the Delete action but truly was the Copy action throwing an error even though it succeeded in copying the document. I have added another question to handle that error.
SharePoint 2010 Workflow Copy Item Action Succeeds but Throws Error