Como te han mencionado, cualquier herramienta te vale. Personalmente, Photoshop es de lejos la mejor opción por tema de potencia. También es la más complicada.
Si estás haciendo un rom hack pues en el propio Advance Map/ la herramienta que sea. Si es para un engine, el mismo tiene herramientas de tileado (ya sea Game maker, RMXP, Unity...)