This is definitely a viable idea. To give you some information from the linked Wikipedia article:
Cleaning symbiosis in our nature
Cleaning symbiosis is a mutually beneficial association between individuals of two species, where one (the cleaner) removes and eats parasites and other materials from the surface of the other (the client). Cleaning symbiosis is well-known among marine fish, where some small species of cleaner fish, notably wrasses but also species in other genera, are specialised to feed almost exclusively by cleaning larger fish and other marine animals. Other cleaning symbioses exist between birds and mammals, and in other groups.
So while you will mostly find this behaviour when looking at small and bigger fish you will also come across cases where birds and mammals are living in such a symbiosis.
While it's often the case that you can find cleaning stations instead of riding with the host there is no reason to think that this should be the case with herds roaming through large forests.
Cleaners eat parasites - but sometimes also mucus and tissue
It's important to note that in fish for example the cleaner will often also eat mucus and tissue from the client and if the cleaner is too aggressive the client may stop the interaction - which may cause the cleaner to die, as they are often cleaning predatory fish that would normally eat them. You could add this to your alien creatures to show that the relationship between the individuals is important. Especially when the Honey Mouths are always with the Thorn Shredders it's important that either side keep an eye out for the other, because if the cleaner dies the client may die because of parasites or because he doesn't get enough syrup. After some time they may depend on this food source. And the cleaners may die if the client dies as they are not fast enough to keep up with the herd on their own.
Thorn Shredder death would be problematic for his surviving Honey Mouths
Another important fact is how the herd will for example handle the case of a dying Thorn Shredder - this leaves up to fifteen members of the Honey Mouths without food. They may distribute those to other members where the new Honey Mouths have to arrange with the existing ones. Or maybe they will fight with each other. Or they will simply try to keep up and wait for a place to become available.
You need pouches for baby Honey Mouths
As you have a cleaner species that is always with the client it's also important to keep an eye our for baby cleaners. They are extremely small in comparison with the client and you might want the client to have some niches or similar parts where baby Honey Mouths can be safely stored and fed by their parents without having to fear falling down. The amount of baby Honey Mouths might also be important to the client, as the client will not get as much syrup when the syrup has to be fed to the baby Honey Mouths and it's additional weigth, slowing down the Thorn Shredder and thereby making it more difficult for the Thorn Shredder and all the Honey Mouths to survive. The same goes for Thorn Shredder babies of course.
The amount of baby Honey Mouths can for example be regulated through pouches of the Thorn Shredder (thanks to G0BLiN for this idea). Each pouch is big enough for exactly one baby Honey Mouth to be nursed. This also helps when then grow - a young Thorn Shredder would have none or maybe one pouch, a bigger one can maybe have up to five. Only when a pouch is available will the Honey Mouth be nursed. If there are too many the others will simply die.
These pouches can be used to capture pregnant wild Honey Mouths
Or the pregnant Honey Mouth transfers to a different client with a pouch that is available. This way there could be a fluctuation of Honey Mouths in the Thorn Shredder herd. And it may also be a way to capture Honey Mouths - just place a couple pouches on a dummy Thorn Shredder and put the pregnant Honey Mouths there with some food.
Honey Mouth colouration should indicate "Here be yummy syrup"
In fish you will often find a blue striped coloration - independent of where exactly you are looking. This convergent evolution might be interesting for you, too. Your animals don't want to be too obvious, because they are always with their client and therefore don't need to attract other clients. Maybe they are very good at looking like tree branches, thereby increasing the camouflage. Or if the Thorn Shredders are so big that this is not really needed, which I take from your descriptions that they are leaving destroyed forests in their wake, you might want to add special colouration to them. A little yellow pattern on their back maybe or something else that symbolises "Here be yummy syrup".
You could have parasites that are very similar to Honey Mouths but feed mostly on tissue
This is also fascinating because you could have evil twins - parasites that look like Honey Mouths and feed like Honey Mouths, but don't feed the Thorn Shredders like Honey Mouths. This can be found in nature, too. They look like cleaners, but mostly feed on tissue while others do the cleaning. These are more difficult as your Honey Mouths would surely find them and want to get rid of those parasites, too. But maybe you have a special Honey Mouth species that specialises on not-being-picked at the evening and mainly eats tissue while the normal Honey Mouths do the work. If they sometimes feed the Thorn Shredders they could just as well merely be lazy Honey Mouths.
Herds need to meet to exchange Honey Mouths
The biggest problem is finding new Honey Mouths when yours died because of a disease for example. They are not living anywhere specifically, so your Thorn Shredders can't go looking for them. I recommend that different herds meet at regular intervals to exchange Honey Mouths - which is good for the gene pool of the Honey Mouths and might give your herd the ability to give Honey Mouths away if there are too many or get some if there are too few.
Baby Thorn Shredders inherit Honey Mouths from their mother
A similar problem arises when new Thorn Shredders are born. A newborn Thorn Shredder needs some Honey Mouths to be clean and not get infected. The best solution would be to have the mother Thorn Shredder give one of her Honey Mouths to her young. This makes room for another Honey Mouth on her, which might trigger the Honey Mouths to create another one. Once the new Honey Mouth is old enough to live on his own the young Thorn Shredder will be older and has enough place and parasites to shoulder a second Honey Mouth - as the Thorn Shredders are much bigger they will likely live a lot longer and mature more slowly.
Baby Thorn Shredders might also be a way for the herd to handle having too many Honey Mouths. It probably doesn't hurt to give a young Thorn Shredder one or two extra Honey Mouths, as long as you don't give a newborn Thorn Shredder a dozen Honey Mouths he will still be able to keep up with the herd and feed his Honey Mouths. Maybe it will be a bit harder and the young Thorn Shredder will have to stay close to his mother so that his Honey Mouths can forage some of the trees that are destroyed by the mother.
If you want to capture Thorn Shredders you can lure them in by being a Honey Mouth Exchange - or make that a tourist attraction
Thorn Shredder herds will seek out other herds that have Honey Mouths to give away when their supply is short or herds that need Honey Mouths when they have too many. This is perfect for you, because those probably long-living, giant, free-roaming Thorn Shredders will surely get to know you and your friends at the station or restaurant. Whenever they have too many Honey Mouths they will try to come to you to give them away because they know you will take them. When they have too few they will come to you to get some. Even if there is no need to get more or less Honey Mouths, as I have already mentioned it's beneficial for the Honey Mouths to change their clients from time to time so that their gene pool is more diverse.
These large, slow creatures will be detectable far in advance so you can easily check which state they are in and prepare accordingly. Treat them fairly, or basically just ignore them, and they will give you a fresh supply of wild-born Honey Mouths. Maybe you can make a tourist attraction out of this: Once per year a giant herd comes to trade their Honey Mouths.
Conclusion
It's a difficult balance because your cleaners are always travelling with the same client, but there is no reason why it should not work as you have protrayed it.
