The problem is the ' before '((((class color...
The quote in front basically means that nothing will be evaluated, so you weren't actually using a string.
To fix it use a backquote:
`((((class color ... (:background ,evil-search-highlight-background-colour) ...

Thank you @naclander , I learned something! However now I have the problem that I can't override the default value - it always takes the default (yellow1). I assume the problem got to do with evaluation time, I tried different versions with backticks, single quotes, defun with no luck :(

From my init.el:

(setq evil-search-highlight-string-min-len 2) ;;works
(setq evil-search-highlight-background-colour "purple1") ;; doesn't work

After making the changes you suggested:

(defvar evil-search-highlight-background-colour "yellow1" "background colour of highlighted text")
(defface evil-search-highlight-persist-highlight-face
  `((((class color))
     (:background ,evil-search-highlight-background-colour)))
  "Face for the highlighted text."
  :group 'evil-search-highlight-persist)

For reference, here's the block that's using the min-length attribute that I can configure fine:

(defvar evil-search-highlight-string-min-len 1 "min legth")
(defun evil-search-highlight-persist-mark ()
  (let ((hlt-use-overlays-flag t)
        (hlt-last-face 'evil-search-highlight-persist-highlight-face)
        tmp)
    (if isearch-regexp
        (progn
          (setq tmp (car-safe regexp-search-ring))
          (setq evil-search-highlight-regex-flag t))
      (progn
        (setq tmp (car-safe search-ring))
        (setq evil-search-highlight-regex-flag nil)))
    (if (>= (length tmp) evil-search-highlight-string-min-len)
          (hlt-highlight-regexp-region-in-buffers tmp (list (current-buffer)))
      ))
  (setq evil-search-highlight-regex-flag t)
  )

Hi guys,

Please note that currently this project is unmaintained because I went back to Vim and anyway I wasn't very good at elisp. If some of you want to take over it please fork and we can update the elpa links. I'll update the readme.

@juanjux Sure thing, I forked it.

@mpollmeier You have to put the setq before loading evil-search-highlight-persist. Also, change your defvar to defcustom.

Thank you, that did the trick. I made evil-search-highlight-string-min-len a defcustom as well for consistency.