For the manx cat at least, it isn't a naturally-selected trait. It's a partially-dominant trait which mutated spontaneously, and then humans on the Island kept breeding these cats with short/no tails together until they took over the island. If you breed a manx cat with a non-manx cat, some of the kittens will have no tail or a shorter tail...etc. From my understanding this was in the mid 19th century, so basically an accident of nature combined with a Victorian penchant for peculiar pets. I'm not sure about the sheep, but they are a much more ancient breed...