Can you please customize the variable `TeX-style-private' to a directory
of your choice, save the file there, restart Emacs and open your test
file and report back if it works?  I will install the patch afterwards.

In case you're interested in the changes:

--8<---------------cut here---------------start------------->8---
diff --git a/style/cleveref.el b/style/cleveref.el
index 2774dcbd..c241a1cc 100644
--- a/style/cleveref.el
+++ b/style/cleveref.el
@@ -1,6 +1,6 @@
 ;;; cleveref.el --- Style hook for the `cleveref.sty' package.

-;; Copyright (C) 2014--2016, 2018 Free Software Foundation, Inc.
+;; Copyright (C) 2014--2019 Free Software Foundation, Inc.

 ;; Author: Matthew Leach <matthew@mattleach.net>
 ;; Maintainer: auctex-devel@gnu.org
@@ -47,22 +47,41 @@ string."
           (labels-string (mapconcat #'identity labels ",")))
       (TeX-argument-insert labels-string optional))))

+(defun TeX-arg-cleveref-crossref-type (optional &optional prompt)
+  "Insert the cross-reference type for macros of cleveref package.
+If OPTIONAL is non-nil, insert the resulting value in brackets.
+Use PROMPT as the prompt string."
+  (let* ((type (mapcar #'list
+                      '("appendix" "subappendix" "subsubappendix"
+                        "subsubsubappendix" "subfigure" "subtable"
+                        "subequation")))
+        (types (append type (LaTeX-counter-list))))
+    (TeX-argument-insert
+     (completing-read (TeX-argument-prompt optional prompt "Type") types)
+     optional)))
+
+(defvar LaTeX-cleveref-label-regexp
+  '("\\\\label\\[[^]]*\\]{\\([^\n\r%\\{}]+\\)}" 1 LaTeX-auto-label)
+  "Regexp matching a \\label incl. an optional argument.")
+
 (TeX-add-style-hook
  "cleveref"
  (lambda ()
+
    (TeX-add-symbols
+    ;; 4 Typesetting Cross-References
     '("cref" TeX-arg-cleveref-multiple-labels)
     '("Cref" TeX-arg-cleveref-multiple-labels)
     '("crefrange" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
     '("Crefrange" (TeX-arg-ref "key (first)") (TeX-arg-ref "Key (last)"))
-    '("cpageref" TeX-arg-cleveref-multiple-labels)
-    '("Cpageref" TeX-arg-cleveref-multiple-labels)
-    '("cpagerefrange" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
-    '("Cpagerefrange" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
     '("cref*" TeX-arg-cleveref-multiple-labels)
     '("Cref*" TeX-arg-cleveref-multiple-labels)
     '("crefrange*" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
     '("Crefrange*" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
+    '("cpageref" TeX-arg-cleveref-multiple-labels)
+    '("Cpageref" TeX-arg-cleveref-multiple-labels)
+    '("cpagerefrange" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
+    '("Cpagerefrange" (TeX-arg-ref "Key (first)") (TeX-arg-ref "Key (last)"))
     '("namecref" TeX-arg-ref)
     '("nameCref" TeX-arg-ref)
     '("lcnamecref" TeX-arg-ref)
@@ -70,7 +89,18 @@ string."
     '("nameCrefs" TeX-arg-ref)
     '("lcnamecrefs" TeX-arg-ref)
     '("labelcref" TeX-arg-cleveref-multiple-labels)
-    '("labelcpageref" TeX-arg-cleveref-multiple-labels))
+    '("labelcpageref" TeX-arg-cleveref-multiple-labels)
+    ;; 6 Overriding the Cross-Reference Type
+    '("crefalias" TeX-arg-counter "Type")
+    '("label" [ TeX-arg-cleveref-crossref-type ] TeX-arg-define-label)
+
+    ;; 8.1.2 Customising Individual Cross-Reference Types
+    '("crefname" TeX-arg-cleveref-crossref-type
+      "Singular name" "Plural name")
+    '("Crefname" TeX-arg-cleveref-crossref-type
+      "Singular name" "Plural name")
+    '("creflabelformat" TeX-arg-cleveref-crossref-type t)
+    '("crefrangelabelformat" TeX-arg-cleveref-crossref-type t))

    ;; These macros aren't used particularly often during the course of
    ;; normal referencing.
@@ -79,26 +109,48 @@ string."
     "namecref" "nameCref" "lcnamecref" "namecrefs" "nameCrefs"
     "lcnamecrefs" "labelcref" "labelcpageref")

+   ;; Add \label[type]{label} to AUCTeX parser
+   (TeX-auto-add-regexp LaTeX-cleveref-label-regexp)
+
+   ;; Tell RefTeX.  Check if `reftex-label-regexps' is bound and use a
+   ;; local version of it.  Check if the regexp is already added in
+   ;; order not to run `reftex-compile-variables' every time the style
+   ;; hook runs
+   (when (boundp 'reftex-label-regexps)
+     (unless (member "\\\\label\\[[^]]*\\]{\\(?1:[^\n\r%\\{}]+\\)}"
+                    reftex-label-regexps)
+       (add-to-list (make-local-variable 'reftex-label-regexps)
+                   "\\\\label\\[[^]]*\\]{\\(?1:[^\n\r%\\{}]+\\)}"
+                   t)
+       (reftex-compile-variables)))
+
    ;; Fontification
    (when (and (fboundp 'font-latex-add-keywords)
              (eq TeX-install-font-lock 'font-latex-setup))
-     (font-latex-add-keywords '(("cref" "*{")
-                               ("Cref" "*{")
-                               ("crefrange" "*{{")
-                               ("Crefrange" "*{{")
-                                ("cpageref" "{")
-                                ("Cpageref" "{")
-                                ("cpagerefrange" "{{")
-                                ("Cpagerefrange" "{{")
-                                ("namecref" "{")
-                                ("nameCref" "{")
-                                ("lcnamecref" "{")
-                                ("namecrefs" "{")
-                                ("nameCrefs" "{")
-                                ("lcnamecrefs" "{")
-                                ("labelcref" "{")
-                                ("labelcpageref" "{"))
-                             'reference))
+     (font-latex-add-keywords '(("cref"          "*{")
+                               ("Cref"          "*{")
+                               ("crefrange"     "*{{")
+                               ("Crefrange"     "*{{")
+                               ("cpageref"      "{")
+                               ("Cpageref"      "{")
+                               ("cpagerefrange" "{{")
+                               ("Cpagerefrange" "{{")
+                               ("namecref"      "{")
+                               ("nameCref"      "{")
+                               ("lcnamecref"    "{")
+                               ("namecrefs"     "{")
+                               ("nameCrefs"     "{")
+                               ("lcnamecrefs"   "{")
+                               ("labelcref"     "{")
+                               ("labelcpageref" "{")
+                               ("label"         "[{"))
+                             'reference)
+     (font-latex-add-keywords '(("crefalias"            "{{")
+                               ("crefname"             "{{{")
+                               ("Crefname"             "{{{")
+                               ("creflabelformat"      "{{")
+                               ("crefrangelabelformat" "{{"))
+                             'function))

    ;; Activate RefTeX reference style.
    (and LaTeX-reftex-ref-style-auto-activate
--8<---------------cut here---------------end--------------->8---

Best, Arash