Is the unauthorized deletion of data considered a breach of integrity or availability?

However, one of my colleagues disagrees and considers such to be an attack on the Integrity principle, because data was modified by being destroyed without authorization.

Your colleague has a point. Unauthorized data deletion is foremost a breach of integrity since deletion can be considered a special case of modification. This can have an impact on availability, but it doesn't have to. E.g, an attacker who manages to delete all logfiles on a web server probably wouldn't impact the server's uptime. But obviously a breach of integrity often implies impaired availability since a service with corrupted resources will likely not function properly.

I wouldn't always force a vulnerability into one of the three CIA categories, though. The impact of unauthorized data deletion is quite obvious, so I'm not sure categorizing it according to the CIA triad adds any clarification. Also note that there are many alternative models such as the Parkerian hexad that give you a few more options to choose from.

In my opinion you shouldn't put a vulnerability into the CIA triad. Because if you do then you have to put it in all of these three criteria. For example:

Confidentiality: When there is a vulnerability in your system, any unauthorized person can access your system and your data are no longer secret, which violates confidentiality.

Integrity: If an intruder exploits the vulnerability and deletes/modifies some/all data, then it violates Integrity.

Availability: If intruder deletes/modifies all/some data and users don't get those data/any service because of that then this situation violates Availability.

So it would be best if you categorize a vulnerability based on its type (e.g. Memory leak), severity (e.g. High), impact (root privilege escalation) etc.

In my opinion, your colleague is right. Unauthorized modification/deletion of data is considered a breach or loss of integrity since the data is no more intact. The aftermath of this could result in unavailability as availability may or may not be affected in all cases. For example, if a user A's login credentials were deleted then he won't be able to access his account. This is affecting availability and integrity. However, user B can still access his account regardless. This is only affecting integrity. In both cases, the data is not consistent anymore, i.e. integrity is lost.

Hope this helps :)