If you've been constrained to 500 days, essentially you already have your estimate. Your client has time-boxed your activity. Time-boxing is a common (and Agile way) to set a budget.
Now, if we take the 500 man days as our budget, then assume we'll have 4 developers (equating to 125 working days - assuming no absence), so we've fixed two vertices of the cost-time-quality project management triangle:
So, we're left with scope as the only variable for our product - this is where estimation comes in. We need to ensure that what you'll be able to deliver within those constraints will satisfy your client.
To do that, you'll need to be able to break the requirements down into high-level stories that you can then categorise (by priority) into critical (MVP), core and optional features of your scope.
You'll first need to estimate each of the critical stories that will form your minimum viable product. You can start with story-points or other relative sizing activities initially, but you'll eventually have to form an estimate in days of effort.
The temptation is usually to apply a conversion factor from your relative sizing to days of effort (e.g. 3 story points equals 1 day). Don't do this! Instead, use the relative sizing to discuss and refine your work estimates.
Once you have your high-level estimates for your MVP, you'll be able to assess whether the time-box will realistically give your team the opportunity to deliver the client's vision. If the MVP estimate came out at say, 200 days (effort), repeat the exercise for the remainder of the core and optional features.
If the estimate for your MVP, core or optional features pushes the estimate beyond the time-box, you'll need to start negotiating with your client. If it's just the MVP alone that's big enough to break the time-box, you'll either need your client to agree to a smaller scope or increase their budget (which may involve questioning the feasibility of the project)...
If it's either the core or (more) optional features that don't fit into the time-box, the client will need to prioritise them - in the full knowledge that if work completes faster or slower than the estimates, they'll get more or less of these features - but they'll get the ones most important to them first.
Alternatively, you may be able to demonstrate that if they allowed more time / resources / teams, you'd be able to deliver more of what they want:
To gain more confidence in your estimates, your client may agree to a few "pilot" iterations (Sprints) - or they may just agree to let your team start the product in its entirety. This is where velocity tracking comes in.
After each iteration, you'll know how many story-points have been delivered. From there, you'll be able to begin tracking and forecasting your burn-down rate. Remember that burn-down is non-linear, so don't treat the estimates your team gave as deadlines, but do monitor the velocity trend. You can use this information to provide clear visibility to your client as to whether your efforts are on track (and manage their expectations or react to any deviation).