How about using System.ComponentModel.Backgroundworker component? Not sure how to use it though..
progress bar ... Unfortunately I am using only one delete statement.
Do the delete on a background thread, compile this to a DLL, include in your app:
http://www.c-sharpcorner.com/UploadFile/akmccarter/CSharpTetris11292005014807AM/CSharpTetris.aspx
and just tell the user "Hey.. Why not see how many lines you can get while I delete those records?"