Near the end of the first chapter, when the animals sing this song, Orwell writes the answer himself to your very question... at least in part:
The singing of this song threw the animals into the wildest excitement. Almost before Major had reached the end, they had begun singing it for themselves. Even the stupidest of them had already picked up the tune and a few of the words, and as for the clever ones, such as the pigs and dogs, they had the entire song by heart within a few minutes. And then, after a few preliminary tries, the whole farm burst out into 'Beasts of England' in tremendous unison. The cows lowed it, the dogs whined it, the sheep bleated it, the horses whinnied it, the ducks quacked it. They were so delighted with the song that they sang it right through five times in succession, and might have continued singing it all night if they had not been interrupted.
In this passage, we see that the "stupid" animals could pick it up because of the tune and some of the words. To me, this means that familiar sounding 'Clementine' and 'La Cucaracha' motivated the animals. The language of the song must have pleased them as well. No matter how dumb an animal or person is, if you give them what they want to remember, it is easier to remember.
Other reasons for the ease of remembrance this passage shows include the facts that every animal could sing it in their own way, and they repeated it 5 times.