Spikes, Assumptions, and Assessments
On investigating this it seems the general consensus is that it is impossible to accurately estimate this without knowing factors of scope, scheduling, and quality. They are not happy with this answer.
Stakeholders are rarely happy with the reality that poor-quality specifications lead to inaccurate estimates. There are a few potential solutions to this common issue:
Bound your estimate with documented assumptions.
As an example, you might base your estimates around other similar projects (or a collection of projects). Itemize your assumptions about scope, resource requirements, and quality of deliverables, and clearly state that your estimate is based on those assumptions holding true throughout the project life-cycle.
Perform a paid assessment with a documentation deliverable.
Make the first part of your engagement an assessment where you delve into the project's specifications and assumptions. For example, perhaps you could engage for two weeks to craft a more-accurate estimate of the total project based on the additional information you gather during the assessment.
Spike a solution.
In agile projects, one often uses a time-box to sketch out a prototype or explore a potential design. Crafting a wireframe or prototype will often give you enough insight into an epic to refine your estimate based on some real data, and provide additional detail about the project's underlying assumptions.
You can mix and match estimation solutions, either with some of the examples listed above or with other methodologies. Regardless of how you proceed, though, the goal should be to provide a sufficient basis for assigning a confidence interval to your estimates that have some reasonable chance of success based on your documented assumptions.
Because the cone of uncertainty is so high at the start of a project like this, it is important to document your estimation methodology as well. That way, the means by which you arrived at your estimate are clear to both the stakeholders and the project team, often improving everyone's comfort level with the estimate itself.