Since Sun first suggested it, you should probably use Pluggable Authentication Modules (PAM). The C example in the documentation (warning, PDF link) shows how to add an extra layer to the password changing process. Your assignment is to wrap the API in XS so that I can use perl to develop PAM plugins ;-) (The PAM stuff on CPAN is only for using PAM, not for extending it.)
Update: Looks like there is already a logging plugin which you can download and compile (tarball link).
Update: You will want logging on the password stack, not the login stack. Other than that, traveler's node probably points you at the quickest (and most perl-y) solution. (++)
The intelligent reader will judge for himself. Without examining the facts fully and fairly, there is no way of knowing whether vox populi is really vox dei, or merely vox asinorum. — Cyrus H. Gordon
