SELECT col1, col2 FROM tab1
UNION
SELECT colA, colB from tab2
ORDER BY col1 || NULL , col2 || NULL;

Does this work? It should use the column names from the first part of the union query (col1, col2) above.
The || NULL should turn off the index? Can you post an explain plan of the slow query and the fast query?

Frank