Hi Lee

I tried deleting a Certification and the course completion records were retained for the user. 

The other option is to unassign the user from the certification so a record of the certification structure is still there in case this is needed in the future.

If you unenrol the user from the course then they will lose most of there course progress depending on the unenrol action selected 

I think it pays to test to see that the deletion actions are what you want and do a backup beforehand as it is hard to know what future compliance requirement may be needed.

Regards