My favourite illustration about design processes is the following:
Don't even care about where does it come from, it's the long-forgotten old-style software design (when there wasn't separate UX and technical design, there was software engineering, and engineering processes), but it still holds the key.
As you see, all start roughly at the beginning, but their intensity is changing. These are about 2-4 week iterations.
There's no first or last: we could say: started first, or finished first.
Personally, I'd feel, that you should start with functionality, as it defines what the system is used for.
But on the other hand, users speak user language, that is, user interface. They can only explain it within a familiar environment, and that's usually GUI. In the terms of change requests, it always comes either as UI changes, or based on a strange mental-implementation model, the users' model of the system's perceived implementation.
In any way, the point is to stick to needs, not to buttons: your users don't need another button (even if they say that), they have a new problem which they want to solve with the button. Make sure you record that information, as early as possible.
Because buttons come and go, problems remain the same. Applications are about problems. They are about how to solve non-computer related needs how to reach non-computer related goals.
Your specification should be a clear systematic record of the system of these needs, just how Linné tried to describe the system of living things: your world to describe is a world full of needs and drives.
An elegant solution is the one which matches its counterpart, the problem effectively, the most simple yet most ingenious way. Elegance is minimalism in beauty.
Designers should strive for elegance, especially when it comes to applications, which are to solve user needs. Everything which doesn't deal with the problem just adds to the problem.
The UI is the system for your users. It's the metaphor of the system.
How could you expect to design an elegant solution system to the problem, if you don't have a clear description of the problem first?
Do whatever you need to understand the problem (if you need UI mockups to help users communicate about those needs, use them, if it's better with diagrams, or text, use them), and do whatever you need to have a solution to that problem, which doesn't want to solve anything else.
For that, I think a key artifact is a requirements document which doesn't detail the solution, on which the actual design of the solution system (which is usually specified in UI terms) is relying. If you design full wireframes first, they hang in the air.
But of course, this is a chicken-or-egg problem. Make sure you have both in your yard at the same time.