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
}