Handling exceptions

Integer.parseInt throws a NumberFormatException when there is a parsing error, you may want to consider catching that and then just output the validation status as "Invalid".

Field names

final Set<Integer> values = new HashSet<Integer>(Arrays.asList(1, 3, 5, 7, 8, 10, 12));

These aren't just any values, these represent months with 31 days in them. :) Probably call this as monthsWith31Days? I also understand you want to make it clear that these months are obviously unique in the collection (in layman terms), but considering this is only used internally within the method, I don't think there's much harm leaving it as just a List.

Day validation logic

Personally, I will start from the most constrained case and work my way down. The slight advantage is that your 'wider' cases will not need to check that is it not any of the constrained cases (e.g. look at how you do a month != 2 for the first else if branch). In conclusion, this means you can validate for the month of February first, then the 31-day validation, and finally for all remaining months. You can also return immediately from each of the branch, instead of one return statement at the end.

Putting it altogether for DateValidator.isDateLegal()

    private boolean isDateLegal(final String date) {
        final int day = getDay(date);
        final int month = getMonth(date);
        final int year = getYear(date);
        final List<Integer> monthsWith31Days = Arrays.asList(1, 3, 5, 7, 8, 10, 12);
        if (day > 0) {
            if (month == 2) {
                // BTW no need to check if month = 2 here
                return day <= isLeapYear(year) ? 29 : 28;
            } else if (monthsWith31Days.contains(month)) {
                return day <= 31;
            } else if (month > 0 && month < 13) {
                return day <= 30;
            }
        }
        return false;
    }

Regex

Now onto the big one... your regular expression is ideal for simplification by applying the following rules:

• [1-2] can be represented as [12].
• Metacharacters (e.g. .) are interpreted literally in character classes, so there is no need to escape them.
• To match - inside a character class, put it at the last so that it doesn't get interpreted as a range syntax.
• Just as you have used a character class to do your separator replacement for date, you should do likewise for your DATE_PATTERN too.
• In addition to the previous point, you can then apply capture groups to check that the same separator is used.

Putting it altogether for regex

private static boolean isDateFormatValid(final String date) {
    final String DATE_PATTERN = "^([0-9]{2}([./\\s-]?)[0-9]{2}([./\\s-]?)[12][0-9]{3}|" 
            + "[12][0-9]{3}([./\\s-]?)[0-9]{2}([./\\s-]?)[0-9]{2})$";
    final Matcher matcher = Pattern.compile(DATE_PATTERN).matcher(date);
    return matcher.matches() && (Objects.equals(matcher.group(2), matcher.group(3))) 
            && (Objects.equals(matcher.group(4), matcher.group(5)));
}

(BTW, Objects.equals() is a Java 7 method and it is a simple null-safe implementation of calling the first argument's equals() with the second argument. This is important as matcher.group() can return null for non-matches.)

Pro-tip: Actually, you may want to go a step further by grouping the day and year values, and make sure that the length of both parts (i.e. DD,YYYY or YYYY,DD) are different:

private static boolean isDateFormatOk(final String date) {
    final String DATE_PATTERN = "^([0-9]{2}|[12][0-9]{3})([./\\s-]?)[0-9]{2}([./\\s-]?)" 
            + "([0-9]{2}|[12][0-9]{3})$";
    final Matcher matcher = Pattern.compile(DATE_PATTERN).matcher(date);
    return matcher.matches() && (matcher.group(1).length() != matcher.group(4).length())
            && (Objects.equals(matcher.group(2), matcher.group(3)));
}

(Pro-pro-tip: The Pattern can be a private static final field...)

For the validate() method, you can check for a valid format first before validating the entire string:

public boolean validate(final String date) {
    return isDateFormatValid(date) && isDateLegal(date.replaceAll("[./\\s-]", ""));
}