We develop and study the hydrodynamic theory of flocking with autochemotaxis. This describes large collections of self-propelled entities all spontaneously moving in the same direction, each emitting a substance which attracts the others (e.g., ants). The theory combines features of the Keller-Segel model for autochemotaxis with the Toner-Tu theory of flocking. We find that sufficiently strong autochemotaxis leads to an instability of the uniformly moving state (the "flock"), in which bands of different density form moving parallel to the mean flock velocity with different speeds. This instability is, therefore, completely different from the well-known "banding instability," in which bands form perpendicular to the mean flock velocity. The bands we find, which are reminiscent of ant trails, coarsen over time to reach a phase-separated state, in which one high-density and one low-density band fill the entire system. The same instability, described by the same hydrodynamic theory, can occur in flocks phase separating due to any microscopic mechanism (e.g., sufficiently strong attractive interactions). Although in many ways analogous to equilibrium phase separation via spinodal decomposition, the two steady-state densities here are determined not by a common tangent construction, as in equilibrium, but by an uncommon tangent construction very similar to that found for motility-induced phase separation of disordered active particles. Our analytic theory agrees well with our numerical simulations of our equations of motion.