I don't think it matters what size the pics are -- when you choose an image to be a profile pic, it'll show up full size, but the profile pic can only be a square or circle, so you'll need to adjust the framing of the pic to match that area.
Obviously, if you choose a really small low-res pic (like a thumbnail), it will tend to look blurry or pixelated on the phone (especially if it's magnified).