Bechtolsheim stammte aus einer Offiziersfamilie und trat selbst 1907 in die Bayerische Armee ein. Er diente als Hauptmann im Ersten Weltkrieg, anschließend als Kompaniechef und Bataillonskommandeur in bayerischen Reichswehr-Einheiten. Zeitweise gehörte er nach dem Ersten Weltkrieg dem Freikorps Epp an. Nach Bildung der Wehrmacht 1935 zum Oberst befördert, war er zunächst im Ausbildungswesen tätig. 1939 übernahm er ein Infanterieregiment. Im Mai 1941 wurde er zum Kommandeur der in München neu aufgestellten 707. Infanteriedivision ernannt. Diese Division, die vergleichsweise schwach ausgestattet war, wurde von September 1941 als Besatzungstruppe im Raum Minsk eingesetzt, Bechtolsheim selbst zum Wehrmachtkommandanten Weißruthenien ernannt.
Bechtolsheim erließ alsbald radikale Befehle zum Mord an Juden*Jüdinnen und Rom*nja. Nachdem ihm Anfang Oktober 1941 das Reservepolizeibataillon (Pol.bat.) 11 unterstellt worden war, ordnete er die Ermordung aller Juden*Jüdinnen und Rom*nja in den ländlichen Gebieten der Region Minsk an. Allein das Pol.bat. 11 und die ihm unterstellten litauischen Hilfsmannschaften ermordeten innerhalb von zwei Wochen 11.000 Menschen. Weitere 10.000 Menschen wurden durch Bechtolsheims eigene Einheiten, insbesondere das Infanterieregiment 727, umgebracht. Erst am 24.11. stoppte Bechtolsheim die Massenmorde seiner Einheiten, da diese nun von Sicherheits- und Ordnungspolizei übernommen wurden. Doch auch danach befehligte Bechtolsheim Mordaktionen seiner Einheiten, so im Anti-Partisanenunternehmen ‚Bamberg‘ südlich von Bobrujsk im März/April 1942, bei dem 3400 Zivilist*innen erschossen wurden, ohne dass es zu nennenswerten Gefechten gekommen war. Danach kam die Division als Frontreserve zur Heeresgruppe Mitte. Bechtolsheim wurde im März 1943 in die Führerreserve versetzt und anschließend als Wehrersatzinspekteur in Heidelberg eingesetzt.
Anfang der 1960er-Jahre wurden in erster Linie gegen die Bechtolsheim unterstellten Polizeieinheiten strafrechtliche Ermittlungen angestellt, aber nur kurz gegen ihn selbst als den eigentlichen Befehlsgeber. Das Verfahren gegen Bechtolsheim wurde relativ frühzeitig eingestellt.
