site settings > purge wf data should do it.

opt for 'use custom filter' and set condition for state

Here are a couple of blog posts that I was recently reading which attempt to explain the Workflow History Lists:

Demystifying Workflow History (Part 1)

Demystifying Workflow History (Part 2)

From what I understand, NWAdmin.exe can also be used for purging these lists:

NWAdmin Operations - Nintex Workflow 2013

Thanks I have looked at those and it doesn't demystify.

I've used the filter but it doesn't seem to work. I've deleted everything through today and I go back and view Workflow History and I still see the ones that have been "Cancelled" with all their history.

if you go back to purge workflow data page after purge is performed and reapply the same filter, are you provided again with same list of workflow instances?

I've experienced something similar once, when I had quite a long list of instances to be purged.

I managed it to purge it step by step by building extended filter then returned just small subset of all the instances (1 or 2 pages if I recall correctly).

so I would suggest to start with filter for specific workflow instance ID, just to prove cleaning works.

then try to build a filter that will return reasonable amount of instances.

Thanks sounds worth trying.