The thing you need to remember is that Share with me is not a file you actually own that is why this didn't work.
service.Files.Delete(fileId).Execute();
First Get a list of all files in Share with me folder.
var request = service.Files.List();
request.Q = "(sharedWithMe = true)";
request.Fields = "*";
var results = request.Execute();
Find the file you wish to delete:
var myfile = results.Files.Where(a => a.Name.ToLower().Equals("receipt.pdf")).FirstOrDefault();
Now find the permissions on that file associated with the current authenticated user:
var per = myfile.Permissions.Where(a => a.EmailAddress.ToLower().Equals("[email protected]")).FirstOrDefault();
Delete the permissions from the mail file.
service.Permissions.Delete(myfile.Id, per.Id).Execute();
I tested it and it worked. You can just run the initial request though a loop and delete everything if you wish.
Note: This does not appear to work in all cases. I have a file on my Google drive that was shared with me by what appears to be a service account. I have no permissions on the file there for i cant remove my access. I am still digging.