How were the West Berlin air corridors negotiated?

The London Protocol in September 1944 established the occupation zone boundaries which later became the East—West German border and the West Berlin periphery. However, it was not until the early days of July 1945 that those boundaries were actually implemented on the ground. Until then all of Berlin was in the hands of the Soviets, while substantial areas of the future East Germany were actually held by the Western Allies who had taken them in the war, including the city of Leipzig which is located practically halfway across East Germany.

This simultaneous exchange of territory in July 1945 surely would not have proceeded if the Soviets had attempted at the time to hinder the Western Allies' access to their newly acquired Berlin sectors. So it seems likely that the precedent was already set and flights had already taken place, and therefore the agreements in November and December 1945 were simply formalizing the regulatory arrangements for an already exercised right and were merely defining the precise air corridor limitations to be observed from then on. This would be consistent with the fact that these agreements were signed off by relatively low level officials, as mentioned in another answer.

During the Conference Between Marshal Zhukov and Soviet Representatives, General Clay and US Representatives, General Weeks and British Representatives at Marshal Zhukov’s Headquarters on June 29, 1945, the topic of air corridors were briefly mentioned (mostly in context together with road and railway connections through the Soviet Zone):

Marshal Zhukov stated he received requests for railroads from Berlin to Hamburg and Bremen, Berlin–Stendal–Hannover, Berlin–Brandenburg–Magdeburg–Hannover, and a 2½ kilometer rail line within the Russian zone; that he had requests for two highways, one from Berlin through Dessau, Halle, Erfurt, Eisenach, Kassel to Frankfurt, and the other from Berlin–Magdeburg–Braunschweig; and requests for air lanes from Berlin to Bremen as well as Berlin to Frankfurt[/Main].
...

Airfields within Berlin was also discussed during this meeting:

...
The next point for discussion was air ways and rights. Russians stated they gave best airdrome to US and British for conference. Gatow has been designated for full use by both British and American delegations. Russians maintain right of exterior guard and will furnish necessary mess and housekeeping personnel if desired. Guard for fuel hangars, etc., will be responsibility of British and Americans on field. Soviets will exercise no control within the field.

After conference, Gatow becomes British field as it lies within British zone according to Soviet official map. Staaken is in the Russian zone and Russians expected British to give Russians the buildings which are in the British zone. British countered that they had not counted on Gatow and expected to get Staaken from the Russians inasmuch as the buildings were within the British zone. Templehof goes to the Americans which was readily agreed. General Weeks stated that his map supposedly official, did not show Gatow in the British zone. Marshal Zhukov stated flatly that Staaken was not available as it was being prepared for another delegation. Gatow will handle all aircraft incident to conference and all authorities have agreed. British desired Gatow and Staaken airfields considered by Governments later or by the Control Council.
...
General Hill asked for authority to fly in an arc bounded by Hamburg, Berlin and Frankfurt, using whatever direct route to Berlin was required depending on originating point of flight without restriction, and authority to fly 50 miles east of Berlin for instrument landing. Marshal Zhukov stated he would report to his Government that the Americans and British will accept an air lane with the understanding that we operate under US and British regulations, notifying Soviet authorities with the same notice given US and British authorities. For a short while there will be no answer from the Governments; therefore, there should be no problem with previous agreements about aircraft coming into Berlin area. Americans and British will accede to Russian request to notify Soviets one hour before take off time, or arrival over Soviet territory, giving number of aircraft and destination.

Regarding air lanes into Berlin, the main lane from Magdeburg to Berlin will be used. From Magdeburg one lane goes to the southwest to Frankfurt and the other to Hannover to the American and British centers respectively. British and Americans will present the air lane picture to their Governments and give confirmation to Soviets tomorrow.
...

Further topics of this meeting were:

• withdrawal of British and US troops from Soviet Zone
• arrival of British, French and US troops in Berlin
• amount of troops and machinery
• Signal Communications and their maintenance
• radio communications for the Potsdam conference

The Aviation Committee of the Allied Control Council (constituted on the 30th of August 1945) then delt with matters pertaining to air safety.

Report of the Air Directorate on the Creation of a System of Air Corridors To Be Used for Flights in the Respective Zones of Occupation in Germany, 1945-11-22
...
1/ Because of the increasing number of flights between the Greater Berlin area and the respective occupied zones of the four Allied Powers in Germany and because their flights must often be undertaken in conditions of poor visibility or at night, involving risk of collisions; there is a real need to ensure safety of flights over the occupied zones and the Greater Berlin Area by means of a system of air corridors under strict rules of flight for all aircraft using the corridors.
...
3/ The Aviation Committee of the Air Directorate proposes six air corridors over occupied Germany as follows:—

• Berlin–Hamburg
• Berlin–Hannover (Bückeburg)
• Berlin–Frankfurt on Main
• Berlin–Warsaw
• Berlin–Prague
• Berlin–Copenhagen

each twenty English miles wide (ten miles on each side of the centre line of the corridor) which could be used by aircraft of the four Allied Nations with full freedom of action.
...
6/ Consequent on the above, the Air Directorate requests the Coordinating Committee:

1. To confirm the proposals for the establishment of air corridors West of Berlin as follows: Berlin–Hamburg, Berlin–Bückeburg, Berlin–Frankfurt on Main, each twenty English miles wide. Flight over these routes (corridors) will be conducted without previous notice being given, by aircraft of the nations governing Germany.
2. To instruct the Air Directorate to compile rules of flight and means of safeguarding flights along the corridors stated in para. (1) above.
3. To decide in principle or transmit for consideration by appropriate higher authority, the question of the establishment of the air corridors over occupied Germany, Berlin–Warsaw, Berlin–Prague, Berlin–Copenhagen and also the air corridor Bückeburg–Prague proposed by the British representative, as indicated in annexed Map* A). Flights over these routes (corridors) will be conducted by aircraft of the nations governing Germany without previous notice being given.

...

Notes:

• 'Map A' is not available
• the Copenhagen, Prague and Warsaw air corridors were never realised

_{1958 Nato map: LIVE OAK}

Report of the Aviation Committee, Air Directorate, Concerning the Organization of Berlin Air Safety Center, 1945-12-13
...
General Proposals.
1/ Under the designation Berlin Control Zone is understood the air space height up to 10,000 feet above sea level in a radius of 20 English miles from the building of the Allied Control Authority. Also an air space height of 10,000 feet above sea level in agreed air corridors which go out in a radius from Berlin to the borders of the territory of occupied Germany.
...

_{(unknown date) Berlin Control Zone}

Further meetings took place leading to the creation of Flight Rules for Aircraft Flying in Air Corridors in Germany and Berlin Control Zone, 1945-12-31.

This established the:

• 3 air corridors (Frankfurt/Main, Bückelburg and Hamburg)
• width and height in miles,feet/kilometers,meters
  • 20 miles = 32 kilometers
  • 10 miles = 16 kilometers
  • 10000 feet = 3000 meters

The first major dissention between the Soviet and British, French and United States members of the Air Directorate came about during their forty-third meeting:

Report on Extension of Existing Air Corridors in Germany, 1946-05-14
...
The Soviet Member of the Air Directorate dissented in the following statement:

1. The Soviet delegation thinks that the existing system of Air Routes through the Soviet Zone of Occupation in Germany is fully sufficient, not only to meet the requirements of the Allied troops in the sector of Greater Berlin, but also to carry out successfully all the allied transportation needs for commercial cargoes regardless of their volume.
2. The argument put forward by the American delegation concerning the directness of the flights in order to ensure an efficient use of civilian aviation for commercial purposes, cannot be considered convincing, because, the air corridors established by decision of the Control Council of Germany CORC/P(45) 170,39 the air corridors Berlin–Frankfurt-am-Main, Berlin–Buckeburg, Berlin–Hamburg, and the air routes in use Berlin–Copenhagen, Berlin–Prague, and Berlin–Warsaw are direct lines of air traffic and geographical considerations do not permit shortening them.
3. The question of establishing commercial aviation within the boundaries of Germany does not come within the competence of the Air Directorate.

...

Related question:

• world war two - How and why was the boundary between West and East Berlin decided to be where it was? - History Stack Exchange

Sources:

• Enactments and Approved Papers of the Control Council and Coordinating Committee: Military Legal Resources (Federal Research Division: Customized Research and Analytical Services, Library of Congress)
  • Enactments and Approved Papers of the Control Council and Coordinating Committee, 1945, Volume I (PDF)
    • Report of the Air Directorate on the Creation of a System of Air Corridors To Be Used for Flights in the Respective Zones of Occupation in Germany, dated Nov 22.
• Foreign Office, MEMORANDUM Berlin, December 1958 (PDF)
• 1949-08-??: A Report On The Airlift, Berlin Mission; the operational and internal aspects of the advance element : Combined Airlift Task Force (PDF)
• Foreign Relations of the United States: Diplomatic Papers, 1945, European Advisory Commission, Austria, Germany, Volume III - Office of the Historian
  • The complete volume can be downloaded as epub
  • Notes of a Conference, by the Commanding General, First Airborne Army (Parks), 1945-06-29, Document 298
  • Report of the Air Directorate on the Creation of a System of Air Corridors To Be Used for Flights in the Respective Zones of Occupation in Germany, 1945-11-22, Document 1199
  • Report of the Air Directorate on the Creation of a System of Air Corridors To Be Used for Flights in the Respective Zones of Occupation in Germany, 1945-11-28, Document 1201
  • Minutes of the Thirteenth Meeting of the Control Council, Held at Berlin, 1945-11-30, Document 1202
  • Report of the Aviation Committee, Air Directorate, Concerning the Organization of Berlin Air Safety Center, 1945-12-13, Document 1204
  • Minutes of the Eighteenth Meeting of the Air Directorate, Held at Berlin, 1945-12-18, Document 1205
  • Flight Rules for Aircraft Flying in Air Corridors in Germany and Berlin Control Zone, 1945-12-31, Document 1206
• Potsdam Conference - Wikipedia
  • Foreign Relations of the United States: Diplomatic Papers, The Conference of Berlin (The Potsdam Conference), 1945, Volume I - Office of the Historian
  • Foreign Relations of the United States: Diplomatic Papers, The Conference of Berlin (The Potsdam Conference), 1945, Volume II - Office of the Historian
• Foreign Relations of the United States, 1946, The British Commonwealth, Western and Central Europe, Volume V - Office of the Historian
  • Report on Extension of Existing Air Corridors in Germany, 1946-05-14, Document 500
• Foreign Relations of the United States, 1947, Council of Foreign Ministers; Germany and Austria, Volume II - Office of the Historian
• Foreign Relations of the United States, 1948, Germany and Austria, Volume II - Office of the Historian
• Foreign Relations of the United States, 1949, Council of Foreign Ministers; Germany and Austria, Volume III - Office of the Historian
• NATO - Declassified: Code Name - LIVE OAK, 01-Jan.-1958

In particular, why didn't the Soviets refuse to allow air corridors?

"Refusing to allow" would have required the Soviets to enforce that refusal. In other words, having just completed a war with Germany, it would have directly caused a further war with Britain and the US. As good as the Soviet air force were, even a conflict restricted to air superiority was not a fight they could have won; and the US had recently demonstrated what happens if you have air superiority and nuclear weapons. This simply wasn't a hill which the Soviet leadership were prepared to die on.

Also note that no-one foresaw the Berlin Airlift, not even the Allies. Transport planes were seen as a way for moving people or small amounts of equipment. The prospect of using it as a way to supply an entire city wasn't on anyone's radar at the time, because no-one had ever done anything like that before. In theory it should have been obvious, given the payloads carried by heavy bombers, but like many things it is only obvious in hindsight.