Paginar 2 consultas

[repara2]

Te quedaría una cosa así, pero tendrás que probar un poco, no tengo accesso a tu DB:

Código MySQL:

SELECT *
FROM principal
  INNER JOIN categorias
    ON principal.id_categoria = categorias.id_categoria
WHERE categorias.id_categoria =  % s
    AND principal.premium = 0 UNION SELECT *
                                    FROM principal
                                      INNER JOIN categorias
                                        ON principal.id_categoria = categorias.id_categoria
                                    WHERE categorias.IdPadre =  % s
                                        AND principal.premium = 0
ORDER BY id_principal DESC 
UNION SELECT *
                                 FROM principal
                                   INNER JOIN categorias
                                     ON (principal.id_categoria = categorias.id_categoria)
                                 WHERE categorias.id_categoria =  % s
                                     AND premium = 1 UNION SELECT *
                                                           FROM principal
                                                             INNER JOIN categorias
                                                               ON (principal.id_categoria = categorias.id_categoria)
                                                           WHERE categorias.IdPadre =  % s
                                                               AND premium = 1
                                 ORDER BY id_principal DESC