Solved (big up Mary from Microsoft support).
Apparently a SubmitGenerateReport request has to include BOTH Performance Statistics columns and Attributes columns. I was missing an attribute column. This is a working request:
<s:Envelope xmlns:i="http://www.w3.org/2001/XMLSchema-instance" xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
<s:Header xmlns="https://bingads.microsoft.com/Reporting/v13">
<Action mustUnderstand="1">SubmitGenerateReport</Action>
<AuthenticationToken i:nil="false">$access_token</AuthenticationToken>
<CustomerAccountId i:nil="false">$account_id</CustomerAccountId>
<CustomerId i:nil="false">$customer_id</CustomerId>
<DeveloperToken i:nil="false">$developer_token</DeveloperToken>
</s:Header>
<s:Body>
<SubmitGenerateReportRequest xmlns="https://bingads.microsoft.com/Reporting/v13">
<ReportRequest i:nil="false" i:type="CampaignPerformanceReportRequest">
<ExcludeColumnHeaders i:nil="false">false</ExcludeColumnHeaders>
<ExcludeReportFooter i:nil="false">false</ExcludeReportFooter>
<ExcludeReportHeader i:nil="false">false</ExcludeReportHeader>
<Format i:nil="false">Csv</Format>
<FormatVersion i:nil="false">2.0</FormatVersion>
<ReportName i:nil="false">Ad Report</ReportName>
<ReturnOnlyCompleteData i:nil="false">false</ReturnOnlyCompleteData>
<Aggregation>Daily</Aggregation>
<Columns i:nil="false">
<CampaignPerformanceReportColumn>AccountId</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>Spend</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>Revenue</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>Conversions</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>AverageCpc</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>Impressions</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>Ctr</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>Clicks</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>ConversionRate</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>TopImpressionRatePercent</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>AbsoluteTopImpressionRatePercent</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>ImpressionSharePercent</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>ImpressionLostToBudgetPercent</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>ImpressionLostToRankAggPercent</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>TopImpressionSharePercent</CampaignPerformanceReportColumn>
<CampaignPerformanceReportColumn>AbsoluteTopImpressionSharePercent</CampaignPerformanceReportColumn>
</Columns>
<Scope i:nil="false">
<AccountIds i:nil="false" xmlns:a1="http://schemas.microsoft.com/2003/10/Serialization/Arrays">
<a1:long>$account_id</a1:long>
</AccountIds>
</Scope>
<Time i:nil="false">
<PredefinedTime i:nil="false">Yesterday</PredefinedTime>
</Time>
</ReportRequest>
</SubmitGenerateReportRequest>
</s:Body>
</s:Envelope>