I took the liberty of writing some code that actually is tail-recursive. I removed the function from the signature because you can always apply that to the resulting queue. I also created a trait called Node which I think makes the code a little bit nicer:

trait Node[T] {
  val value: T
  val children: Seq[Node[T]]
  def preOrder: Queue[T]
}

case class Tree[T](value: T, children: Seq[Node[T]]) extends Node[T] {
  def preOrder: Queue[T] = {
    @tailrec
    def inner(queue: Queue[T], nodes: Seq[Node[T]]): Queue[T] = nodes match {
      case Nil => queue
      case tn :: tns => inner(queue.enqueue(tn.value), tn.children ++ tns)
    }
    inner(Queue.empty.enqueue(value), children)
  }
}