I just tried the rpm2cpio+cpio approach but that too didn't work.
One difference I noticed is that if I build giflib from source, it installs the .so files in lib/.
But if I extract from the cpio, they get installed in lib64/ (Note that I had to extract from both giflib rpm and giflib-devel rpm because giflib-devel rpm lib64 simply had symbolic links which are supposed to link to the .so files extracted from the giflib rpm).
I updated LD_LIBRARY_PATH to include the new lib64/ dir.
That leads me to a question: Just as we have LIBOTF_CFLAGS, LIBOTF_LIBS, can we not have LIBGIF_CFLAGS and LIBGIF_LIBS?
I tried setting LIBGIF env var to "-L/path/to/the/lib64 -lgif" before doing ./configure.. but that did not help.
Something else is not right in my system.. but at least I am glad I can still build emacs, be it without gif.
configure finds the gif_lib.h, I find that GifMakeMapObject reference in that .h but somehow configure thinks that it's not there.
My package building fu is limited to this so I cannot debug why configure thinks that GifMakeMapObject is not found in -lgif.