We have studied morphology and phase segregation of AlInP shells on GaAs nanowires. Photoluminescence measurements on single core-shell nanowires indicated variations in the shell composition, and phase segregation was confirmed by cross-sectional scanning transmission electron microscopy on 30 nm thin slices of the wires. It was discovered that Al-rich domains form in the <112> directions where two {110} shell facets meet during growth. We propose that the mechanism behind this phase segregation is a variation in the chemical potential along the circumference of the nanowire together with a difference in diffusion lengths for the different growth species. From the morphology of the core and the shell, we conclude that the side facet growth is temperature dependent forming {112}facets at low growth temperature and {110} facets at high growth temperature.