How to send little data between admin pages of my plugin?

Go with your last idea – generate a URL like so:

$raw_url = admin_url( 'admin.php?page=add-edit-record&edit-id=' . $id );
$esc_url = esc_url( $raw_url ); // For href attributes and the like

And then in your handler for add-edit-record:

if ( ! empty( $_GET['edit-id'] ) && $id = absint( $_GET['edit-id'] ) ) {
    if ( ! $record = get_record( $id ) )
        wp_die( 'Nope' ); // Or something similar
}