makeinfo is part of the texinfo distribution.
Get texinfo-*.tar.gz.

However, all GNU distributions should come with prebuilt info files,
thus makeinfo should not be needed.  If you notice a distribution
that does not come with *.info files, please report it as a bug.