Recursive mergesort for a 1000000 shouldn't cause a stack overflow. That's only 20 frames.

It's probably best to rewrite your implementation using the pseudo code on the wiki.

And make some convenience functions so that your sort function doesn't need to wrangle with node links:

struct Node
{
    int data = 0;
    Node* prev = nullptr;
    Node* next = nullptr;
};

struct List
{
    Node* first = nullptr;
    Node* last = nullptr;
    size_t count = 0;

    void append(Node* node);
    void append(List b);
    Node* pop_front();
    explicit operator bool() const
    {
        return !!count;
    }
};

List merge(List left, List right);
List merge_sort(List m);