There is no way to bulk clear out workflow history via the CRM application. It is possible to delete entries under Settings | System Jobs but that is restricted to a set number of records at a time (i.e. the number of records shown in a list view).
In Microsoft Dynamics CRM 4.0 workflow history is stored in two tables called asyncoperationbase and workflowlogbase. Details of all jobs that have run (whether workflow initiated or not) are stored in the asyncoperationbase table. For workflows, asyncoperationbase has one entry.
The systems jobs shown in the application are obtained from the asyncoperationbase table. When system jobs are deleted in the application the corresponding steps in the workflowlogbase table are deleted immediately but the corresponding row in asyncoperationbase is marked for future deletion by changing the value of deletionstatecode to ‘2’ for the appropriate row. Rows that are marked for deletion should be removed by the CRM asynchronous service every 24 hours – however, this does not happen and the only way to remove the rows is by a manual deletion directly in the table using the following SQL statement:
delete from asyncoperationbase where deletionstatecode = ‘2’
Bulk deletion can achieved by using the SDK RetrieveMultiple and Delete messages (see http://node/59) on the workflowlog and asyncoperation entities. Again workflowlog entries are removed immediately but asyncoperation entries are only marked for deletion and have to be removed manually as described above.
Jobs that are suspended or waiting appear to have a statecode of 1.
Also review this Microsoft KB article: http://support.microsoft.com/kb/968520. Update Rollup 3 introduces a registry setting to automatically remove completed workflow logs – see this article http://support.microsoft.com/kb/968755.