We calculate the resistivity and giant magnetoresistance (GMR) of a segmented nanowire consisting of two ferromagnetic segments separated by a thin paramagnetic spacer. Spin-dependent surface electron scattering is taken into account. The quantization of the electron motion due to the small nanowire cross section leads to oscillations of the resistivity and the GMR. The interplay between spin-dependent electron scattering in the bulk and the surface results in a complex behavior of the GMR as a function of nanowire radius and surface-potential strength. Both increase and decrease of the GMR can be obtained as the spin-dependent surface scattering grows.