Help with optimization(scrolling tiled backgrounds)

Would like some help with my scrolling tiled backgrounds.

My game is for mobile and I was wondering what is the max recommended size of a tiled background?

I have 3 right now: (for parallax effect)

bgFront - 512x128

bgMiddle - 512x256

bgBack - 512x256

I was getting horizontal lines but got rid of them by removing the bottom line of pixels in all of them but I thought maybe the lines were there because the images are too big?

Any input on this would be helpful

Thanks!

Those aren't abnormal sizes.

Perhaps it's the device that's the issue.