For sake of discussion, let's be specific in what we mean (and presume you're doing TDD):
- Design is the process of specifying the total shape of your system. You can (and sometimes should) design without directly or indirectly writing a single line of database or program code. You define your Acceptance Tests as the last stage of design.
- Implementation is the process of turning said design into a "working" piece of software. If you're being dogmatic, you wouldn't write a single database index; you'd just define the tables, write the interface object, and rely upon your lower-level platform to load the data. You write Unit Tests and Integration Tests during the implementation, adn the implementation is done when the Acceptance Tests all pass.
- Optimization is making the "working" software you did in Implementation and speeding it up where it runs unacceptably slow. The three layers of test allow you to make changes without breaking anything.
Of course, that's how it works in theory. But as a practical matter, since time and money are both limited, you'll often to the steps out of order. If you expect to need an index on a particular field, there's no reason not to index it as you design it. If while on a binge of coding you realize how you can elegantly solve an alternate usage situation, you can go ahead and code a draft first and write the unit test second. (And when you realize your design is wrong, you'll have go to back and revise your tests anyway.)
As to your particular questions:
Is creating all indexes at the start (design) over engineering?
No, if all are useful indexes and they don't take a significant amount of time.
Yes, if you wind up defining indexes for tables that are days away from even the first rough prototype. (If you create indexes in your initial design, subject them to tests latter on. They may be more trouble than they're worth.)
Should I just skip creating indexes before it's needed because performance issues will show up anyway and probably the indexes that's already been created aren't being used?
No, if it's clear that you'll need to have some columns indexed. If you plan on a feature that searches frequently for stock bids over or under a certain price, you'll probably want an index on the bid value in addition to the record's unique key.
Yes, if it's not clear that the index is going to grant the overall system a performance improvement. The one query a month for bids made by state probably doesn't need a specific index.
Should indexes be treated as part of requirement/specification?
NO. Indexes are a component of the software design. They have no more place in requirements or specifications than usage of a particular framework method or transient variable name.
(It's possible for all or part of the programming to come from your customer, but it's foolish to make use of such a requirement. An index servers no purpose if the server is just going to send the whole table anyway.)