The timer job for purging workflows only deletes workflows and workflow associations, it does not touch the workflow history list. This was better documented for SharePoint 2010, but the behavior seems to be the same in SharePoint 2007.
You can safely delete items pertaining to completed workflows from the workflow history list, but only if you're certain you won't need that information for auditing purposes.
However, the size of the list is not as important as the efficiency of the queries that are hitting it.
Addressing Workflow History List Performance:
To improve performance of the workflow history list, you should add column indexing to your workflow history list. You can add indexed columns by going to List Settings -> Indexed Columns. I recommend adding an index to List ID, Primary Item ID, Workflow Association ID, Workflow History Parent Instance, and Workflow Template ID.
Nitty Gritty Details - What the timer job actually does:
SharePoint does not purge the workflow history after 60 days (that is, from the hidden workflow history list typically found at "[site]/lists/Workflow History"), but rather purges the workflow and the association between the workflow and the workflow history, which involves deleting associated tasks from the task list. It also causes the workflow status column (if it exists) to stop showing a link to the item's workflow history. That's really all that the 60-day purge does.
From Microsoft's documentation (emphasis mine):
By default, Microsoft SharePoint Server 2010 runs a daily Workflow Auto Cleanup job to permanently delete workflow instances and related task entries that still exist 60 days after a workflow is completed or canceled. Workflow history items themselves are not deleted, but the entry point to view them on the status page for a particular instance of a workflow will no longer be available.
The workflow history list itself can get nice and fat without affecting performance since only small chunks of it are safely queried at a time.
