Pokèdex entries state it being able to run over "6,200 miles in a day and night." That's pretty fast. Not enough to Teleport, but still quite speedy.
Another part the Pokédex entries mention is that "It appears in many legends." It "Teleporting" could be a reference to this, as it seems to be "Teleporting" from land to land very quickly.
Another possible reason is that it's labeled as the "Legendary Pokémon." Legendaries typically have Psychic abilities, like teleporting. This is probably the least likely of my three theories, though.
And as always, Gamefreak logic.