We have examined the early stages of self-induced InAlN core-shell nanorod (NR) formation processes on amorphous carbon substrates in plan-view geometry by means of transmission electron microscopy methods. The results show that the grown structure phase separates during the initial moments of deposition into a majority of Al-rich InAlN and a minority of In-enriched InAlN islands. The islands possess polygonal shapes and are mainly oriented along a crystallographic c-axis. The growth proceeds with densification and coalescence of the In-enriched islands, resulting in a base for the In-enriched NR cores with shape transformation to hexagonal. The Al-rich shell formation around such early cores is observed at this stage. The matured core-shell structure grows axially and radially, eventually reaching a steady growth state which is dominated by the axial NR growth. We discuss the NR formation mechanism by considering the adatom surface kinetics, island surface energy, phase separation of InAlN alloys, and incoming flux directions during dual magnetron sputter epitaxy.