How to delete a large amount of nodes effeciently during cron?

I would not recommend using Cron for this task.Since you have so many nodes it would always time out. Your better off using Drush and the Delete All module.

Or if you're fully purging all your nodes for instance I have written an SQL script before I can invoke with Drush which uses the sql truncate command to remove all data from Fields of a content type and then does a delete all from node and node_revisions for the given content type, and url aliases -- etc. Using SQL makes such a task take very little time for hundreds of thousands of nodes.

EDIT:

The Delete All admin UI has options for a quick delete that uses sql JOINs and not node_delete. See the admin form code: http://cgit.drupalcode.org/delete_all/tree/delete_all.module#n71

I suggest you install and try using the module.