I had the best luck stealthing to within 10 or so tiles of the slime then shadow jumping next to it. The slimes have a fairly large reveal distance, so shadow jump is the key. Usually I could get 2 things dyed before they would run off. Though if you hide as soon as they are about 10 tiles distant they seem to stop moving. Only problem is that other players cannot see you, of course, and they may chase away your prey.
All in all it is good fun to watch everyone run this way and that trying to chase down a slime of a particular color, and the cursing when the slimes invariably change color right when the player is about it strike.
Good luck!