In order to get a prelink.conf, you have to have FEATURES="prelink" in your make.conf. This is not documented in the prelink howto, nor is it documented in the large FEATURES comment in make.conf. Reproducible: Always Steps to Reproduce: 1. Look at the docs :P
It should also mention that /etc/prelink.conf is not generated automatically by portage, but by env-update (yes, okay, part of portage, but it's not obvious since the text seems to imply that emerging prelink will automatically generate /etc/prelink.conf which it does not).
there is no such thing as FEATURES="prelink" from portage.py: if spawn("/usr/sbin/prelink --version > /dev/null 2>&1",free=1) == 0: prelink_capable=1