If you can run Apex, here's how you assemble the list for the destructiveChanges.xml very quick. Note: replace { and } by corresponding angle brackets.
Copy paste the debug statements into your destructiveChanges.xml file.
List{String} objectTypes = new List{String}{
SomeCustomMetadataType__mdt.getSObjectType().getDescribe().getName(),
AnotherCustomMetadataType__mdt.getSObjectType().getDescribe().getName()
};
System.debug('\t{types}');
for (String objectType : objectTypes) {
List{SObject} customMetadataRecords = Database.query('SELECT DeveloperName FROM ' + objectType);
for (SObject customMetadataRecord : customMetadataRecords) {
String recordName = (String)customMetadataRecord.get('DeveloperName');
System.debug('\t\t{members}' + objectType + '.' + recordName + '{/members}');
}
}
System.debug('\t\t{name}CustomMetadata{/name}');
System.debug('\t{/types}');