We systematically investigate the chemical vapor deposition growth of graphene on Ge(110) as a function of the deposition temperature close to the Ge melting point. By merging spectroscopic and morphological information, we find that the quality of graphene films depends critically on the growth temperature improving significantly by increasing this temperature in the 910-930 {deg}C range. We correlate the abrupt improvement of the graphene quality to the formation of a quasi-liquid Ge surface occurring in the same temperature range, which determines increased atom diffusivity and sublimation rate. Being observed for diverse Ge orientations, this process is of general relevance for graphene synthesis on Ge.