I'd suggest the following workaround instead: delay mlocate-updatedb.service startup for a few minutes (e.g. 10 minutes) so that if it need to run at system boot, it is started after awhile.
The following will do this, and it won't be replaced if mlocate package is updated:
mkdir /etc/systemd/system/mlocate-updatedb.service.d
cat <<EOF > /etc/systemd/system/mlocate-updatedb.service.d/mlocate-updatedb.conf
[Service]
ExecStart=
ExecStart=/bin/sleep 10m
ExecStart=/usr/libexec/mlocate-run-updatedb
EOF
This has the advantage that it should prevent slow boot (Not tested yet, but it should do so, and also will still update locate database everyday.
For Fedora 23 with systemd-222-14.fc23.x86_64 (and above): systemd timers now have a new option: RandomizedDelaySec, which seems to provide the solution for this problem.So, adding a line like this should fix the problem too: RandomizedDelaySec=30m
(Notice that the delay is still random, so sometimes it might be very small and cause slow boots.)
Update: An update is pushed to Fedora testing repository, which seems to have changed service type from oneshot to simple. This will cause systemd to not wait for updatedb termination before continuing. This somewhat solves the problem too. However, I'd still suggest using a sleep or RandomizedDelaySec so that it'll not run during boot at all; because its heavy IO would still slow-down the boot process.