There should be a traceroute protocol whereby a "specially marked packet" is understood to be traceroute, and generates an ICMP response even though its TTL is still positive. The ICMP response will carry the observed TTL value.
Then one packet will get all the echoes in one go instead of having to send a tirade of packets with increasing TTL values.