予算はどうやって決めればいいですか？

複数のオプションがありますので紹介します

投資可能額を元にする。ソフトウェアを作るというのは投資してリターンを期待してのものです。なので投資可能額というのはある程度決まることもあります。それを聞いて、そのまま予算にするというのがオプション1
従来のやり方に近い形で積算して、それを予算にする。ただしあくまでも規模感や予算の算出のためだけに使うのであって、スコープを保証するわけではない。

既存の組織文化との関係

なお、既存の予算制度自体がアジャイルと相容れないところも多いです。
不確実性の高いプロダクト開発は失敗もします。したがって、スタートアップへの投資モデルのようなものを適用して、プロダクトがいけそうという確度が上がるにつれて割り当てる予算が増えていく、といった仕組みが相性が良いです。
いきなり組織の制度を変えるのは無理かもしれませんが、そういう予算の考え方が必要だというのを、スクラムマスターとして組織に働きかけるのも重要かと思います。

契約について

まず大前提として「一括請負」の形式はスコープが可変であることで価値を出すアジャイル開発（当然スクラムも含みます）と相性がよくありません。アジャイル開発でも見積もりを行いますがFP法などのボトムアップによる詳細な見積もりをしません。見通しが立てられる程度のざっくりした見積もりを行い、これは当たらないことを前提としています。ですので予算（あくまでも予定）を立てることはできますが、その見積もりが “お見積もり” として一人歩きしないよう、契約としては慎重になるべきです。経営観点での発展的な考え方として、脱予算経営という考え方が注目されています（ユーザーが予算の情報を元に投資の戦略を立てる）。

顧客の要望を聞いた上でアジャイルが向くと判断したならアジャイルの提案になるでしょう。ただ、顧客の関心は手法ではなく成果なので、手法を推すというより想定する成果を推します。その成果を得るにはアジャイルなやり方が必須なのです、という提案になるでしょう。最近だと「アジャイルで」と手法を指定する発注者も増えてきていますが、発注者の理解が乏しく「アジャイルで」が早い安い旨い定額無制限食べ放題を意味している場合があり、気をつける必要があります。
発注側としてアジャイルを採用した場合は、WFのような従来型の一括発注のようなラクができません。頼んだ通りのQCDSであとはよろしく、ができないからです。とはいえ、頼んだ通りのQCDSになるかどうかは、蓋を開けてみるまでわかりません。どんなプロダクトかにもよりますが、そのプロダクトの開発にアジャイルが向いているならば、SESのような形で関わってくれるベンダーを探すのが良いかと思います（一括請負がフィットしないのはすでに書いた通りです）。