I wish to remove all the mix-sell product links in the store - we've around 22,000 links that evolved as the result of the auto mix sell extension which i have since removed.

I imagine it's something related to getting rid of records in the table catalog_product_link?

Or it is possible to method of doing this programmatically?

You're right, getting rid of records may be the quickest method of doing this. Begin by searching at catalog_product_link_type and discover the link_type_id for "mix_sell". It's often "5" but there's pointless to take a risk.
Backup your database.
Remove all records from catalog_product_link having a matching link_type_id. An SQL such as this should work:

DELETE FROM `catalog_product_link` WHERE `link_type_id` = 5;

should you rather not edit the database directly, you could utilize the free extension from TBT known as Mass Product Relater. That will help you to strip out product associations in the Manage Items power grid.