If a part is destroyed, all connections to it should be cleaned up as well, including tags.
CollectionService tags shouldn’t cause memory leaks.
Delete a tag whenever you’re absolutely sure you’re not going to add any more items into it anymore. Even then, empty tags (tags with no parts connected to them) shouldn’t cause any memory leaks; if they do, it’s most likely negligible to performance.
If the part is destroyed, you don’t need to worry about disconnecting any connections to the part, it’s done automatically. You can disconnect it manually when you destroy it though just to be safe.
You don’t have to do anything here. This isn’t going to cause a memory leak unless you keep stacking connections to the part. If it’s one part that’s never going to change or be destroyed, all you need to do is connect all your connections once.
A guide to memory leaks: