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 it is, probably you removed the .info files (perhaps by typing make realclean or make maintainer-clean), or accidentally or purposefully modified the Texinfo sources. In those cases, reretrieving the distribution will get them back. Otherwise, it's a bug in the distribution, and you should report it as such.