We show that for shear flow of an upper convected Maxwell fluid with small but nonzero slip velocity, an increasing dependence of the slip velocity on the elastic normal stress,in the flow direction leads to short wavelength flow instability at sufficiently high Weissenberg number (greater than or similar to 10). Pressure-dependent slip can also lead to instability, but only at unrealistically large Weissenberg number. If the slip velocity depends only on shear stress, then the flow is always stable. These analytical results are valid in a specific asymptotic limit, but are independent of the specific form of the mc,del for slip. Numerical results for specific, phenomenological slip models and the Phan-Thien-Tanner bulk constitutive model show that the results are robust in the presence of nonlinear viscoelasticity. The scaling of the critical shear stress for instability with modulus and molecular weight and of the distortion period with polymer relaxation time are qualitatively consistent with experimental observations of the sharkskin instability in linear polyethylenes. The results may also have some relationship to the recent experimental observation of short wavelength instability in plane Couette flow of an entangled solution with wall slip. (C) 1999 American Institute of Physics. [S1070-6631(99)00207-X].