I do indeed see this behavior on 6.1, with as few as a couple hundred environments.
On 6.2 (Puppet 3.8.6), I can confirm this is fixed. I've tried with up to 10,000 environments:
[root@sat-rhel7 environments]# for i in `seq 1 10000`; do mkdir -p Environment$i/modules; done
[root@sat-rhel7 environments]# time puppet cert list --all
+ "sat-rhel7.example.com" (SHA256) 58:3A:31:45:B4:98:9C:35:9C:F6:39:06:75:E6:43:6A:54:62:8B:7B:EC:46:11:21:A3:8E:B2:4F:D1:A0:CA:FD (alt names: "DNS:puppet", "DNS:puppet.example.com", "DNS:sat-rhel7.example.com")
real 0m0.881s
user 0m0.835s
sys 0m0.044s