I'm trying my best to catch a Taillow in Omega Ruby, but I can't find one. Looking at the locations here, he is most likely to appear in area 1 of Route 104 instead of area 2, but which part of Route 104 is area 1?
The first part of Route 104 is before Petalburg Woods, where Mr. Briney's cabin is. The second part is after Petalburg Woods and leads into Rustoboro City. You can find Tailow in the grass around Mr. Briney's cabin or before the entrance to the woods.
Source: Experience and Serebii