private void move(int direction, State current, List<State> neighbours) {
    State next = current.move(direction);
    if (!seen.contains(next)) {
        neighbours.add(next);
    }
}

I'm not convinced that this is the real source of the performance problem. Checking six million states should not take that long.

I'd really like to see more of the code and perhaps try running it. Did my changes help? Hurt? Make no difference? Fail compilation? Break other things? I can't test most of that at all, and testing compilation would be complicated enough that I don't want to make the effort.

The hope is that a more aggressive check of the seen tracker would help here. Other than that, this shouldn't make much difference.

private void move(int direction, State current, List<State> neighbours) {
    State next = current.move(direction);
    if (!SET.contains(next)) {
        neighbours.add(next);
    }
}

The hope was that a more aggressive check of the seen tracker would help here. Other than that, this shouldn't make much difference.

    @Override

    public boolean contains(Object obj) {
        State v = (State) obj;
        for (State mad : this) {
            if (Arrays.equals(mad.getState(), v.getState())) {

                return true;
            }
        }
        return false;
    }

So every time you call SET.contains or SET.add (which calls contains), you do an Arrays.equals on each and every member of the SET. You took an \$\mathcal{O}(1)\$ operation and turned it into a \$\mathcal{O}(n)\$. Why? You could have just made this a List with the same performance. Instead of overriding HashSet.contains, consider what happens if you override State.hashCode.

                current = QUEUE.remove();

                SET.add(current);

You also call SET.add ever time you remove something from the queue. And you remove every valid state from the queue. I.e. \$\mathcal{O}(n)\$ times. So now we're up to \$\mathcal{O}(n^2)\$. You only add to the queue once without adding to the set. So just move the SET.add to where you put the initial state in the queue.

                    if (!SET.contains(n)) {

                        SET.add(n);
                        if (!QUEUE.contains(n)) {
                            QUEUE.add(n);
                        }
                    }

You can trim this down.

                    if (!SET.contains(n)) {
                        SET.add(n);
                        QUEUE.add(n);
                    }

You don't need to check if it's in the QUEUE. You only add things to the QUEUE after you put them in the SET. So this will never be true and is a linear time operation.

Also, as I said earlier, I'd prefer to do that check earlier.

Example

    public static final int WIDTH = 4;
    public static final int SIZE = 16;

    private static Set<State> SET = new HashSet<>();
    private static Queue<State> QUEUE = new LinkedList<>();

    public static void main(String[] args) {
        long initial = 0x1FFF56FF9AFFDFF0L;

        State s = new State(0, initial, 0);
        SET.add(s);
        QUEUE.add(s);

        int numInserted = 0;
        while (!QUEUE.isEmpty()) {
            numInserted++;
            if (numInserted % 1024576 == 0) {
                System.out.println(numInserted + " " + QUEUE.peek().getMoves());
            }

            findNeighbours(QUEUE.remove());
        }

        System.out.println("Recorded inserted :" + SET.size());
    }

    public static void findNeighbours(State current) {
        int i = current.getEmptyIndex();
        int column = i % WIDTH;
        if (column > 0) {
            move(-1, current);
        }
        if (column < WIDTH - 1) {
            move(1, current);
        }
        if (i >= WIDTH) {
            move(-WIDTH, current);
        }
        if (i < SIZE - WIDTH) {
            move(WIDTH, current);
        }
    }

    private static void move(int direction, State current) {
        State next = current.move(direction);
        if (!SET.contains(next)) {
            SET.add(next);
            QUEUE.add(next);
        }
    }

    public static class State {

        public static final int BIT_WIDTH = 4;

        int moves;
        Long composition;
        int emptyIndex;

        public State(int moves, long composition, int emptyIndex) {
            this.moves = moves;
            this.composition = composition;
            this.emptyIndex = emptyIndex;
        }

        public int getMoves() {
            return moves;
        }

        public void setMoves(int moves) {
            this.moves = moves;
        }

        public long getState() {
            return composition;
        }

        public int getEmptyIndex() {
            return emptyIndex;
        }

        public State move(int direction) {
            int index = getEmptyIndex();
            long next = swapBits(composition, index, index + direction, BIT_WIDTH);
            return new State(getMoves() + 1, next, index + direction);
        }

        public long swapBits(long n, int from, int to, int width) {
            from *= width;
            to *= width;
            long xor = ((n >> from) ^ (n >> to)) & ((1 << width) - 1);
            return n ^ ((xor << from) | (xor << to));
        }

        @Override
        public int hashCode() {
             return composition.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }

            if (!(o instanceof State)) {
                return false;
            }

            State s = (State)o;
            return composition.equals(s.getState());
        }

    }

I ripped out the database parts, since I don't have access to the database. It was still slow, so I don't think that was the problem.

Because this overrides hashCode, we can just use the regular hashSet. Long.hashCode seems to work well enough.

This version does a million records in less time than the original took to do 20 thousand. And it doesn't take longer with each added element.

I tested it with output for the simple, one and two square states. I just printed out the number found for the states with more squares.

Note that your example has seven squares and 57,657,600 states, not 5 million.

In this example, I used F (15) instead of -1 to represent unknown squares. That of course stops working if 15 is one of your squares.