How to override WordPress registration and insert an auto-generated username?

One alternative is to modify the $_POST['user_login'] input value when submitting new registration form, that is before WP process the registration form. A good hook to achieve this is login_form_register that fires before processing and rendering registration form. login_init also works but need more work to make sure we are on register action.

add_action('login_form_register', 'custom_user_login');
function custom_user_login() {

    // make sure regisration form is submitted
    if ($_SERVER['REQUEST_METHOD'] != 'POST')
        return;

    // base of user_login, change it according to ur needs
    $ulogin = 'random-user';

    // make user_login unique so WP will not return error
    $check = username_exists($ulogin);
    if (!empty($check)) {
        $suffix = 2;
        while (!empty($check)) {
            $alt_ulogin = $ulogin . '-' . $suffix;
            $check = username_exists($alt_ulogin);
            $suffix++;
        }
        $ulogin = $alt_ulogin;
    }

    $_POST['user_login'] = $ulogin;
}