[SalesForce] Easiest way to delete a million records

Been doing tests in sandbox in which I've created about a million accountshares that I need to get rid of for testing.

I'm trying data loader in bulk api mode to export than delete but I keep getting:

InvalidBatch : Failed to process query: QUERY_TIMEOUT: Your query request was running for too long. Trying again later.;

Not sure if I should be waiting longer? Any other options or dataloader configurations I should be looking at?

EDIT

I've been trying with batch apex jobs yet still having issues.

Script

string str='select id from AccountShare where lastmodifiedbyid =\'0050P000007Kfy2\' limit 10000';
sharedeletebatch bdt=new sharedeletebatch(str);
Database.executeBatch(bdt);
system.debug(bdt);

Batch

global class sharedeletebatch Implements Database.batchable<sobject>
{

     global final string query;
     global sharedeletebatch(string q){

          query=q;
     }

     global Database.QueryLocator start(Database.BatchableContext BC){

      return Database.getQueryLocator(query);
     }
     global  void execute(Database.BatchableContext BC,List<SObject> scope){
         delete scope;

    }
    global void finish(Database.BatchableContext BC){
    }


}

First error: [REQUEST_RUNNING_TOO_LONG] Your request was running for too long, and has been stopped.