Primer error cuando llamas a may(Q,N,X) en la regla de la tercer linea, luego estas tratando de pisar X con X is X+1. Dicha asignacion en Prolog no esta permitida ya que no se pueden modificar "Variables" con valores ya asignados.
Segundo te devuelve falso porque cuando may(N,[H|Q],X):-H>N,may(Q,N,X),X is X+1. compara 1>4 da falso y como no puede entrar en las otras reglas(ya que una es con una lista vacia y la otra si solo tiene un elemneto) tira false y el backtracking te devuelve false.
En prolog lo que se usa y para mi es muy util para entender el funcionamiento es escribir trace. en el prompt para ir viendo como se esta ejecutando el programa y con nodebug. se sale del modo trace.
Tu programa seria el siguiente:
mayor(_,[],0).
mayor(N,[H|Q],X):- H>N, mayor(N,Q,X1), X is X1+1.
mayor(N,[H|Q],X):- H=< N, mayor(N,Q,X).
El uso del guion bajo es para que no de el warning de Singleton. Su funcion es otra, pero para no enredarte solo te digo lo antes mencionado, como veras yo creo una variable X1 en la segunda linea para poder guardar la cantidad de valores que cumplieron la condicion de mayores, y luego en el de abajo llamo cuando son menores que N porque sino, cuando apenas se encuentre con un menor comenzara el backtracking y cortara la recursividad, arrojando false.
Espero que se entienda y cualquier cosa me respondes.