You've obviously never seen a router taking 15-25 kpps out on an
interface change a major portion of the routing table to point
somewhere else due to a circuit glitch on that outbound interface. In
earlier versions of some routers the whole router dies. With no ICMP
rate limiting you'd need to generate 25 kpps of ICMP until routing
converged. That could be a fair amount of work.
Some routers send ICMP to another processor that mainly handles the
routing protocols and doesn't forward very well. Some routers keep it
on the same card and pass it up to an IP process and incur IPC
overhead rather than doing it directly. These are both slower than
the primary forwarding path.
The NSS used to do ICMP generation on the forwarding cards just as
fast (or slow) as they forwarded packets, so it is possible.
Curtis