Is almost nothing on a P3 800Mhz running Linux 2.4.20. Using Benchmark.pm and system("program.pl") the former runs at 3875.97 times per second and the latter runs at 3906.25 times per second. The env binary is only 11 Kbytes and should fit in RAM for any program executed frequently. The env binary also only runs exec(), it does not run fork(), so sensible systems (such as Linux) that do not need to reschedule a timeslice to complete exec() show almost no penalty at all (I suspect the slight penalty is due to the loading of the elf information and performing a dependency analysis of the shared libraries associated with /usr/bin/env).
As I mentioned in my response, one of the reasons why /usr/bin/env would be necessary is the case where perl is network-mounted and a shell script is necessary to select the correct version of perl to execute for the host platform. In this case, the issue is that it would be impossible or impractical to do this sort of thing any other way.
As for portability, env is located in /usr/bin/env on HP-UX, SunOS, Solaris, and Linux. If perl can easily have a symbolic link created at /usr/bin/perl, then env can easily have a symbolic link created at /usr/bin/env on whatever architecture you happen to be referring to that does not have /usr/bin/env.