Viscoelastic effects have a strong effect on interfacial stability, which is very important in coextrusion of polymers. Elastic instabilities tend to be far stronger than their Newtonian counterparts. The study of two-layer flows is accessible to asymptotic methods when one of the layers is thin. This has been carried out for Newtonian flows, and is extended in the first paper to the substantially more complex problem of weakly nonlinear stability of core-annular flow of two upper-convected Maxwell liquids. The annular layer is thin and has a different relaxation time and constant viscosity to the core liquid which it encapsulates. We derive novel nonlinear evolution equations which describe the spatio-temporal motion of the interface between the two fluids. We present numerical results which show how the stratification in elasticity can have either stabilizing or destabilizing effect on the flow. We also show how, in the limit of long wavelength disturbances at least, an additional jump in the viscosities can lead to a transition from an unstable regime to one in which organized traveling wave pulses which move in the axial direction. These traveling waves have multiple characteristic length scales.