Stai ancora confondendo il concetto di lista con quello di suoi elementi. Una lista è il contenitore generale, mentre un suo elemento è una struttura con payload e puntatore all'elemento successivo.
Visto poi che la tua coda era di fatto implementata come una lista, la puoi riciclare praticamente in blocco, eventualmente sistemando un pochino quello che era elem in modo che sia gestibile dall'esterno:
codice:
class lista
{
  public:
    //Elementi memorizzati all'interno
    class elemento
    {
      private:
        // Payload
        char info;
        // Puntatore all'elemento successivo
        elemento * next;
        
      public:
        // Costruttore di default - inizializza la struttura a valori "neutri"
        elemento() :
            info('\0'),
            next(NULL)
        {
            return;
        };
        
        // Costruttore parametrico - inizializza la struttura con il valore desiderato
        elemento(char Info) :
            info(Info),
            next(NULL)
        {
            return;
        }; 
        
        // Getters/setters
        // payload
        char get_info() { return info; }
        void set_info(char Info) { info = Info; }

        // elemento successivo
        elemento * get_next() { return next; };
        void set_next(elemento * Next) { next = Next; }
        
        // ultimo elemento
        elemento * get_last()
        {
            if (next == NULL)
                return this;
            elemento * ret;
            for (ret = next; ret->get_next() != NULL; ret = ret->get_next())
                ;
            return ret;
        }
        
        // Qualche altro metodo di utilità generale
        
        // Attacca l'elemento passato e tutti gli elementi ad esso collegati
        // dopo l'elemento corrente, riattaccando il next attuale in fondo
        void append(elemento * elem)
        {
            if(get_next()!=NULL)
            {
                elemento * last=elem->get_last();
                last->set_next(next);
            }
            set_next(elem); // fine del gioco
        }
    };

  private:
    // Testa della lista; è un puntatore ad un oggetto 'elemento'
    elemento * testa;

  public:
    // Costruttore di default - inizializza una lista vuota
    lista()
    {
        testa = NULL;
    }

    // Distruttore - dealloca tutti gli elementi
    ~lista()
    {
        char dummy;
        while (testa != NULL)
        {
            remove(dummy);
        }
    }

    // Stampa il contenuto della lista
    void stampa(ostream & os);

    // Inserisce in fondo alla lista un valore
    void append(char dato);

    // Estrae dalla testa della lista un elemento; restituisce true se il dato è stato estratto, false se la lista è vuota
    bool remove(char & output);
    
    // Fornisce il primo elemento
    elemento * get_testa() { return testa; }
    // Fornisce l'ultimo elemento
    elemento * get_last()
    { 
        return testa==NULL?NULL:testa->get_last();
    }
};

void coda::append(char dato)
{
    elemento * nuovo = new elemento(dato);

    if (lista == NULL)
        lista = nuovo;
    else
        lastelem()->append(nuovo);
}

bool coda::remove(char & output)
{
    if (lista == NULL)
    {
        return false;
    }
    else
    {
        elemento * daRimuovere = testa;
        output = lista->get_info();
        testa = lista->get_next();
        delete daRimuovere;
        return true;
    }
}

void coda::stampa(ostream & os)
{
    if (testa == NULL)
    {
        os << "La coda e' vuota!\n";
    }
    else
    {
        os << "La coda contiene i seguenti elementi: \n\n";
        elemento * temp = get_testa();
        while (temp != NULL)
        {
            os << "---> [ " << temp->get_info() << " ] ";
            temp = temp->get_next();
        }
        os << "\n\n";
    }
}
Con questi strumenti ora diventa molto più facile scrivere una funzione di unione, ma, ribadisco, mi devi spiegare come deve funzionare questa fusione di liste: la nuova lista deve contenere tutti gli elementi delle due liste come copia degli elementi oppure deve semplicemente prenderne possesso e lasciare le altre due liste vuote?