Comment author: @garrigue

There is a misunderstanding here.
The problem is not with the type definition, which does not have to be
regular for datatypes (only type abbreviations are restricted).
The problem is just that your expected type requires polymorphic
recursion, which is known to be undecidable.
Moreover your type annotation is misleading, since in ocaml type variables
appearing in annotations may be freely instantiated by the typechecker.
Since 3.12, polymorphic recursion is allowed, using a new form of type
annotation, which makes polymorphism requirements explicit.
The following code will give you the expected type.

let rec connected : 'a 'b. ('a -> 'b -> bool) -> ('a, 'b) bijective_map -> bool

fun r -> function
| Nil -> false
| Cons(a,b,l) -> r a b or connected (fun x y -> r y x) l;;