Ok, I’m re-doing my response as I’m pretty sure I figured out everything that’s going on here 
As @ninjapenguin mentions, if you have a tag and delete all of the topics that have that tag applied, the tag remains listed on the tags page and the count unchanged. I believe this is happening because the topics still technically exist and they continue to hold the tag.
@syl if you navigate to the tete tag’s topic list as shown in your screenshot and then add
?status=deleted
to the end of the URL, you should see two deleted topics listed with the tete tag.
The information message in your second screenshot corresponds to the the number of deleted topics that have the tag applied.
I feel like we probably shouldn’t factor in deleted topics when counting/listing tags, but this may not be a super trivial change given how everything is stored in the database. What do you think @codinghorror?